An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality
Authors: Silviu Pitis
Harris Chan
Kiarash Jamali
Jimmy Ba
Venue:  (2020)
Keywords: metric learning
deep metric learning
neural network architectures
triangle inequality
graph distances

Abstract: 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 guarantees---and 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 $\mathbb{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.


Published as a conference paper at ICLR 2020
AN INDUCTIVE BIAS FOR DISTANCES: NEURAL NETS THAT RESPECT THE TRIANGLE INEQUALITY
Silviu Pitis*, Harris Chan Kiarash Jamali, University of Toronto, Vector Institute (spitis, hchan) ecs. foronto.edi
Jimmy Ba
ABSTRACT
Distances are pervasive in machine learning. They serve as similarity measures, loss functions, and learning targets; it is said that good distance measure solves a task. When defining distances, the triangle inequality has proven to be a useful constraint, both theoretically-tto prove convergence and optimality guarantees and empirically-ag 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 Ik", 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
INTRODUCTION
Many machine learning tasks involve a distance measure over the input domain. A good measure can make a once hard task easy, even trivial. In many cases-including graph distances, certain clustering algorithms, and general value functions in reinforcement learning (RL) is either known that distances satisfy the triangle inequality, or required for purposes of theoretical guarantees; e.g.. speed and loss guarantees in k-nearest neighbors and clustering (Cover and Hart 1967 Indyk 1999] Davidson and Ravi 2009), or optimality guarantees for A search (Russell and Norvig 2016). This also makes the triangle inequality potentially useful inductive bias for learning distances. For these reasons, numerous papers have studied different ways to learn distances that satisfy the triangle
inequality (Xing et al. 2003 Yang and Jin 2006 Brickell et al. 2008 Kulis et al. 2013).
The usual approach to enforcing the triangle inequality deep metric learning Yi et al. 2014 Hoffer and Ailon [0115] Wang et al.) 2018) is to use Siamese network (Bromley al. 1994) that computes a Euclidean distance in the latent space. Specifically, the Siamese network models distance dx X X - IR+ domain X' by learning embedding & X' - IR" and computing dx (ar, y) as [|((x) d 2. Successful applications include collaborative filtering (Hsieh et al. 201 7), few-shot learning (Snell al. 2017), and multi-goal reinforcement learning (Schaul et al. 2015). The use of Euclidean distance, however, has at least two downsides. First, the Euclidean architecture cannot represent asymmetric metrics, which arise naturally in directed graphs and reinforcement learning. Second, it is well known that for some metric spaces (X', dx)., including large classes of symmetric graphs (e.g., constant-degree expanders and k-rrgularr graphs). there no embedding Φ that can model dx precisely using || || (Indyk et al. 2017). A classic example is shown in Figure
RR"
In part due to these issues, some have considered non-architectural constraints. He al. (2016) impose a triangle inequality constraint in RL via an online, algorithmic penalty. Implementing such penalty can be expensive, and does not provide any guarantees. An approach that does guarantee
Cooee available https: httpaa//github. com/ / spi s/s///ee deepnorms
spitis/deepnorm

---

Published as a conference paper at ICLR 2020
Norm
MSE
Deep Norm
Wide Norm
Mahalanobis
B
Euclidean, 18", Vn
0.057
2
2
Deep Norm, IR²
0.C0C
Wide Norm, IR2 0.CCC
Fig. 1: The nodes in the graph (left) cannot be embedded into any R so that edge distances are represented by the Euclidean metric: points ((A) and ((D) must lie the midpoint of the segment from (BB) to (Ct)-but then ((A) and (DD) coincide, which incorrect. Our models fit the data in IR? (middle). The visualization (right) shows learned norm balls in red and embeddings in blue.
satisfaction of triangle inequality is fix any violations after learning, as done by Brickell al. (2008). But this does not scale to large problems or provide an inductive bias during learning.
Is it possible to impose the triangle inequality architecturally, without the downsides of Fuclidean distance?
In response this question, we present the following contributions: (1) three novel neural network architectures, Deep Norms, Wide Norms and Neural Metrics, which model symmetric and asymmetric norms and metries, (2) universal approximation theorems for Deep Norms and Wide Norms and modified Input Convex Neural Networks (Amos et al. 2017). and (3) empirical evaluations of our models on several tasks: modeling norms, metric nearness, modeling shortest path lengths, and learning a general value function (Sutton et al., T01T). Our models are guaranteed to satisfy the triangle inequality, straightforward to implement, and may be used in place of the usual Euclidean metric should one seek to model asymmetry increase expressiveness.
2
MODELING NORMS
2.1
PRELIMINARIES
Our goal to construct expressive models of metrics and quasi-metrics on domain X. metric is function d : X x X - Bt satisfying, Vr, y, E X:: MI (Non-negativityy. d(x, y) 2 0.
M3 (Subadditivity). d(x, =) S d(x, v) + d(y, 2).
M2 (Definiteness). d(x, y)
+
M4 (Symmetry). d(z, y) d(y,
Since we care mostly about the triangle inequality (M3), we relax other axioms and define a quasi- metric as a function that is M1 and M3, but not necessarily M2 or M4. Given weighted graph G = E) with non-negative weights, shortest path lengths define a quasi-metric between vertices.
When X is vector space (we assume over IR,, many common metrics, e.g., Euclidean and Manhattan distances, are induced by norm. A norm is a function |-|| X - IR satisfying, Vz, E X, E R+: N1 (Pos. def.). || > O, unless z = O.
N3 (Subadditivity). ||x + yll S || ||y]|
N2 (Pos. homo.). ax| |x]|| [[axz]]. for or 2 0. N4 (Symmetry). ||>||| = -||
An asymmetric norm N1-N3, but not necessarily N4. An (asymmetric) semi-norm is non- negative, N2 and N3 (and N4), but not necessarily N1. We will use the fact that any asymmetric semi-norm || induces a quasi-metric using the rule, d(x, y) || y/|. and first construct models of asymmetric semi-norms. Any induced quasi-metric dl is translation invariant- d(x + z, y + 2) and positive homogeneous-d
ory) = ad((z, y) for a 2 0. If [| is symmetric (N4), so is d (M4). If || is N1, d M2. Metrics that are not translation invariant (e.g.. Bi al. (201)) or positive homogeneous (c.g.. our Neural Metrics in Section 3) cannot be induced by a norm.
convex function f X + a function satisfying C1: ax(x) (1 at). The commonly used ReLU activation, relu(x) max(0, IT), is convex.
Vz, y E X, a E [0, 1]: f(ax+(1-o))
<
2.2
DEEP NORMS
is easy to see that any N2 and N3 function convex-thie all asymmetric semi-norms are convex. This motivates modeling norms constrained convex functions, using the following proposition. Proposition 1. All positive homogeneous convex functions are subadditive; i.e., Cl A N2 = N3.
2

---

Published as a conference paper at ICLR 2020
The proof is straightforward (put N2 to the left side). To use Proposition II we begin with the Input Convex Neural Network (ICNN) (Amos et al. 2017) architecture, which satisfies C1, and further constrain it to be non-negative and satisfy N2. The resulting Deep Norm architecture is guaranteed to be an asymmetric semi-norm. A k-layer Deep Norm defined as:
in C1 and apply
W.
g
fn
h2
|20|| = higs with h;= 9= (W, h1-1 1 U,r) (1)
Deep Norm archirecture N2 for = k. where x is the input, hg = 0, W/ = 0. the activation functions Ge preserve Cl (element-wise), 9k is non-negative, W,+ a non-negative matrix, and U; an unconstrained matrix.
Fig. 2:
As compared to the original ICNN architecture, we have omitted the bias terms from Equation 1 have constrained the g: to preserve positive homogeneity while also allowing them to be any function that preserves element-wise convexity (this is essential to universal approximation results), and have required St to be non-negative.
is easy to verify that the set of valid element-wise 9i is {1) relu(2) + Bx a, 3 0}. This includes ReLUs and leaky ReLUs. But we do not restrict ourselves to element- wise activations. Inspired by GroupSort (Anil et al., 2018), we use activations that depend multiple inputs (and preserve element-wiss C1 and N2). In particular, use the pairwise MaxRel.U:
maxrelu (z. y) [max(ı, y), a relu(z) + relu (y)), where a, 2
Deep Norms are N2 and N3. Using the following propositions, we may also impose N1 and N4. Proposition 2. Ifll I| an asymmetric semi-norm, then ||=||| = |||| ||= x| a semi-norm.
Proposition 3. If lla is an (asymmetric) semi-norm, | 116 is a norm (e.g. || ||A = || l122, and
A >>0 0, then ||x||| A || >||xr||a is an (asymmetric) norm.
2.3
WIDE NORMS
In addition to Deep Norms, we propose the following alternative method for constructing norms: Wide Norm is any combination of (asymmetric) (semi-) norms that preserves N1-N4. is easy to verify that both (1) non-negative sums and (2) max are valid combinations (indeed, these properties were also used to construct Deep Norms), and the vector-wise MaxMean combination valid: max (2,
maxmean 22... Tn.)
Fn) + (1 ax) mean( ..,,.... .nn).
Although the family of Wide Norms is broad, for computational reasons to be discussed Subsection 3.5 we focus our attention on the Wide Mahalanobis norm. References to "Wide Norms" in the rest of this paper refer to Wide Mahalanobis norms. The Mahalanobis norm by W E IR=x", is defined as ||>||]
E IR",, parameterized ||Wr|l2.. It is easily verified that |// is proper norm when W is a non-singular (square) matrix, and semi- norm when W is singular or m < n.
A k-component Mixture of Mahalanobis norm (hereafter Wide Norm, or Wide Norm with k Eu- clidean components) is defined as the maxmean of & Mahalanobis norms:
||>||| maxmean; ([]2)=l|2)
where W; mR with m; S
Wide Norms are symmetric by default, and must be asymmetrized to obtain asymmetric (semi-) norms. We use the below property (Bauer et al. 1961) and propositions (proofs in Appendix (A]. NS. || is monotonic in the positive orthant if < x S (element-wise) implies || s llyll- Proposition 4. If is N5 (semi-) norm 2 then ||| |[eel([ -z)]], where :: denotes concatenation, is an asymmetric (semi-) norm on T
Proposition 5. The Mahalanobis norn with W DU, with D diagonal and U non-negative, is N5.
2.4 UNIVERSAL APPROXIMATION OF CONVEX FUNCTIONS AND NORMS
How expressive are Deep Norms and Wide Norms? Although was empirically shown that ICNNS have "substantial representation power" (Amos al. 2017). the only prior work characterizing the approximation power of ICNNs uses a narrow network with infinite depth, which does not reflect typical usage (Chen et al. 2018). One of our key contributions is series of universal approximation results for ICNNs (with Max activations). Deep Norms and Wide Norms that use a more practical infinite width construction. The next lemma is central results.
3

---

Published as a conference paper at ICLR 2020
Lemma 1 (Semilattice Stone- Weierstrass (from below)). Let C' be set of continuous functions defined on compact subset K of RR"" be a closed subset of C, and f E C. ffr every a E K, there exists 9z E L such that 95 < f and g.x f(x), and (2) L is closed under max (i.e., a, E. I. max(a, b) E L,, then 3h E I. with f on K.
Intuitively, Lemma] I and its proof (Appendix A) say we can approximate continuous f arbitrarily well with family I. of functions that is closed under maximums if we can "wrap" f from below using functions JR with 9s S f Our Universal Approximation (UA) results are now straightforward. Theorem (UA for MICNNs). The family M of Max Input Convex Neural Networks (MICNNs) that uses pairwise max-pooling (or MaxReLU) activations is dense in the family C of convex functions.
Proof. For C, R", let Os M be a linear function whose hyperplane in the graph of is tangent to f at rr Then IN satisfies condition (1) of Lemma [ (because f is convex). The use of pairwise max activations allows one to construct max(h1, h2) E M for any two h1, h2 E M by using (n) max-pooling layers, satisfying condition (2) of Lemma | Thus f' is in the closure of M, and the result follows.
This result applies when MaxReLUs are used, since than max) guarantees that MICNNs can imitate regular ICNNs with at most double the parameters.
set a. B = 0. Using MaxReLU (rather
Theorem (UA for Deep Norms and Wide Norms). The families of Deep Norms (using MaxReLU) and W of Wide Norms (using MaxMean) are dense in the family N of asymmetric semi-norms.
Proof (sketch). The proof almost identical to that of Theorem [ except that here and W contain all linear functions whose graph is tangent any f E N since f is N2. This is easy to for functions defined on IR? See Appendix A for more details.
2.5 MODELING NORMS IN 2D
Having shown that Deep Norms and Wide Norms universally approximate norms, now show that they can successfully learn to approximate random norms on I² when trained using gradient descent. To generate data, we use the below fact, proved Appendix
Proposition 6. The of all asymmetric norms R is in one-to-one correspondence with the set of all bounded and open convex sets ("unit balls" ") containing the origin.
We use Proposition by generating a random point set, computing its convex hull, and using the hull as the unit ball of the generated norm, - ||. We then train different models to approximate || using |D] E {16, 128} training samples of form ((zm, y7), 17), where [|x,, [<r,)]] = and r) ~ (0.885 1.15). The models are trained to minimize the mean squared error (MSE) between the predicted (scalar) norm value and the ground truth norm value. See Appendix C.I for details.
Figure iillustrates the learned 2D norm balls of random symmetric (top) and asymmetric (bottom) norm, for three architectures: Deep Norm, Wide Norm, and an unconstrained, fully connected neural network (MLP). The blue contours in Figure are the ground truth norm balls for values {0.5. 1.5). and black contours the norm balls of the learned approximations. With the small dataset, the MLP
Deep Norm
Wide Norm
MLP
Deep Norm
Widw North
MLP
16
-0-
(a) Small Dataset (k = 16)
(b) Large Dataset (I- = 128)
Fig. 3: Visualization of learned 2D norms (top) and asymmetric norms (bottom). Blue contours are the ground truth norm balls for values (0.5, 1, 1.5), and black contours the learned approximations.
4

---

Published as a conference paper at ICLR 2020
N1 (M1-2)
N2 (Homo.)
N3
N4
UA
Notes
(M3)
(M4)
Euclidean
/
MLP
X
X
X
x
Deep Norm
*
*
Wide Norm
*
/
*
works large minibatches 3.5 based on Deep Norm or Wide Norm
Neural Metric
*
*
*
Table 1: Norm (metric) properties of different architectures. As compared to Euclidean architectures, ours are universal asymmetric semi-norm approximators (UA) and can use propositions to optionally satisfy (*) N1 and N4. Neural metrics relax the unnecessary homogeneity constraint metrics.
overfits to the training data and generalizes poorly, while Deep Norm and Wide Norm generalize almost perfectly. With the large dataset, we observe that Deep Norms and Wide Norms generalize to larger and smaller norm balls (due being N2), whereas the MLP is unable generalize the 0.5 norm ball (indeed, MIP (0.5) 0). While the symmetric Wide Norm fits well, the results suggest that the asymmetrized Wide Norm is not effective as the naturally asymmetric Deep Norm. See Appendix for additional details and visualizations.
3 MODELING METRICS
Having constructed models of asymmetric semi-norms R", now use them to induce quasi- metrics on domain X. As the geometry of X's raw feature space will not, in general, be amenable to favorable metric (indeed, the features need not be in IR",, assume the Siamese network approach and learn an embedding function, á A - IR... A Deep Norm or Wide Norm || lle. with parameters 0, is defined on _ and the metric over is induced e y) = (| o(x)) lla.
We could also define || lle using an unconstrained neural network (MLP), but this would not be guaranteed satisfy the norm axioms and induce a quasi-metric
To illustrate this approach, we revisit Figure I To get the results shown, we represent the four nodes as one hot vectors and embed them into I2² using ((x) Wx, W E R2x1 We then define the norm on IR2 as either a Mahalanobis norm, Deep Norm, or Wide Norm. Training the norm and together, end-to-end with gradient descent, produces the Figure T results.
The choices are summarized in Table I While Deep Norm and Wide Norm have similar properties, the depth of the former suggests that they can learn efficient, hierarchical representations (as do deep neural networks); however, Wide Norms have computational advantage when computing pairwise distances for large minibatches, which we explore in Subsection 3.5 Since inducing metrics with Deep Norms Wide Norms produces potentially unnecessary homogeneity constraint (due to N2), the next Subsection considers Neural metrics, which offer an approach to relaxing this constraint.
3.1 NEURAL METRICS
Instead of inducing a metric with a norm, we could define a metric directly as non- non-negative weighted sum of different metrics. E.g., we did for Wide Norms, of k deep Euclidean metrics. all components of a Wide Metric are norm-induced, however, it can be induced directly by single Wide Norm with A components, by setting d(x) to be the concatenation of the (x)x,, and using each W, to select the indices corresponding to ój. It follows that for a family of Wide Metrics to be more expressive than the family of norm-induce metries, must include components that are either not translation invariant or not positive homogeneous. We consider the latter, and use the propositions below to modify our norm- indu-idduedd metrics (proofs in Appendix (A)
define Wide Metric the mean
Proposition (Metric- preseriip concave functions). If d X x X - R is (quasi-) metric, f: IR - Rt. f (0) = {0}. and is concave (i.e., f f is convex), then f d is (quasi-) metric. Proposition 8 (Max preserves metrics). If dj and d2 are (quasi-) metric, so too is max(d1, d2).
To use Proposition / we note that each unit in the final layer a Deep Norm defines a metric (assuming 9k-1 is non-negative, it is when using ReLU MaxReL. activations), does
5

---

Published as a conference paper at ICLR 2020
each component of Wide Norm. Thus, by applying mneric-preservvngg functions f; to these metrics, and then combining them using MaxMean, mean or max, we obtain a valid metric, which name Neural Metric. Our k-component f, parameterized by Wx, bj I as follows: fa(x)) = ming [Wsz + bij): where wij 2 0, b.j 2 0, by =
The advantage of Neural Metrics over plain Deep Norms and Wide Norms is that model certain metrics, such as d(z, y) = (1. x yll). This type of metric might be induced by shortest path lengths in fully connected graph with some maximum edge weight (for example, navigation problem with teleportation device that takes some constant time to operate).
better
3.2 APPLICATION: METRIC NEARNESS
We now apply models the metric nearness problem (Sra et al. 2005 Brickell et al.) 2008). In this problem, we are given matrix of pairwise non- metric distances between (finite) objects, and it is desired to minimally repair the data to satisfy metric properties (the triangle inequality, M3, in particu- lar). Formally, given data matrix D IR**" we seek metric solution X E R8xx that minimizes the "distortion" JANN = || - DI|2/|1 DI12 (normalized distance) to the original metric. Sra et al. (2005) proved this loss function attains its unique global minimum in the set of size n discrete metrics and proposed an ( triangle fixing ("TF") algorithm for the symmetric case, which iteratively fixes M3 violations and is guaranteed converge to the global minimum. (WN) based Neural Metrics) achieve results comparable the symmetric case. We note that TF, which approaches the solution through the space of all n x n matrices, produces non-metric approximation, so that the number of M3 violations (#-M3) is greater than O; this said, it is possible to fix these violations by adding small constant to all entries of the matrix, which does not appreciably increase the loss JMN. To test our models in the asymmetric case, we modified the TFF algorithm; although our modified TF found solution, our DN model performed significantly better. See Appendix D for complete experimental details.
J
# .M3
(S)
JANN
#(4)
MB
2.01e-2
7.7c3
1,30e-1
3.8c2
Eucl
9.12e-2
0
2.02e-1
0
WN
2.44e-2
0
1.86e-1
0
DN
2.00e-2
0
7.29e-2
Table 2: Metric nearness for sym. (S) and asym. (A) matrices in 200 (10 seeds).
(Jshows that for n = 200, our models (Deep Norm (DN) and Wide Norm
that found by 400 iterations of TF in
Although triangle fixing is effective for small n, there is no obvious way to scale it to large datasets or to metric approximations of non-metric distance functions defined on a continuous domain. Using our models in these settings is natural, as we demonstrate in the next subsection.
3.3 APPLICATION: MODELING GRAPH DISTANCES
In the previous subsection we sought to "fix" noisy, but small and fully observable metric; we now test the generalization ability of our models using large (n > 100K) metrics. We do this on the task of modeling shortest path lengths in a weighted graph = (V,E). So long as edge weights are positive and the graph is connected, shortest path lengths discrete quasi-metrics (n [V], and provide an ideal domain for a comparison to the standard Euclidean approach.
Our experiments are structured supervised learning task, with inputs 2, y E V and targets d(ær, v). The targets for a random subset of 150K pairs (of the ((VV?2 total pairs) were computed beforehand
M
[
max((c
ad
Sym?
Euel.
WN
DN,
DNx
MLP
to
278K
611K
145.7
24.5
++
to
12.5
6.6
6.7
6.7
12.3
3d
125K
375K
86.7
13.2
++
3d
31.2
17.3
15.4
12.9
20.6
taxi
391K
752K
111.2
13.4
taxi
14.4
10.6
11.8
11.4
5.8
push
390K
1498K
113.1
14.3
push
22.2
14.0
14.7
13.5
11.3
3dr
123K
368K
86.5
13.1
3dr
22.0
17.5
21.8
18.3
25.5
3dd
125K
375K
97.8
13.4
3dd
211.8
177.1
199.5
157.7
252.7
(a) Graph statistics
(b) Final test MSE @ ID]
50000
Table 4: Graph experiments. (a) Statistics for different graphs. (b) Test MSE after 1000 epochs at training size D = 50000 (3 seeds). The best metric (and overall result if different) is bolded.

---

Published as a conference paper at ICLR 2020
4 8.0om Brv
Room Asym Value
W.delarmm Asym
SE MUP
100
SPL wischomm Agy
SPL NLP
10
08
96
94
Maze Env
Maze Roym Value
SE sellir Boym
SE MIP
SPL Wisetom Any
SLP
16
F
F
5
20
The 4-Room (top) and Maze (bottom) environments, with walls (green), empty cells (red), and agent (blue). The next column shows example ground truth values, where state So denotes agent top left cell. Upper triangular regions indicate the value of ((so, s) while lower indicate V(s,8)) Center: Squared Error (SE) heatmap between the learned and ground truth value for WideNorm and MIP architecture. Right: Success weighted by Path Length (SPL) metric heatmap. Higher is better. See Section 3.4 for detail and Appendix F for more visualizations.
Fig. 4: GVF environments. Left:
using A search and normalized to have mean 50. 10K were used as test set, and the remainder was subsampled to form training sets of size [D] {IK, 2K, 5K, 10K, 50K). Nodes were represented using noisy landmark embeddings (see Appendix D. We compare Wide Norms, Deep Norms (ICNN style, with ReLU activations, DN,), and Deep Norm based Neural Metrics (with MaxReLU and concave activations, DN to the standard Siamese-style S Bromley et al. (1994) deep Euclidean metric and MLPs in six graphs, three symmetric and three not, summarized in Table and described in Appendix D Though MLPs do not induce proper metrics, they are expressive function approximators and serve as relevant reference point. The results (shown for D 50K in Table 3b and expanded upon in Appendix E show that our models tend to outperform the basic Siamese (Euclidean/Mahalannod network, and oftentimes the MLP reference point well.
3.4 APPLICATION: LEARNING GENERAL VALUE FUNCTIONS
In this section, evaluate models the task of learning Universal Value Function A Approxima- tor (UVFA) in goal-oriented reinforcement learning (Sutton et al. 2011] Schaul et al.) 2015). Figure 4 (left) illustrates the two 1 11 grid world environments, 4-Room and Maze, in which our experiments. Each environment has a symmetric version, where the reward is constant (-1), and an asymmetric version with state-action dependent reward. We create a training (s, s', g. d) for the state, next state, goal, reward, and done flag, and the UVFA Vo(s, g) is trained minimize the temporal difference eгrоr via bootstrapped updates with no discounting. We tested several architectures at different training set sizes, which leaves out portion of transitions such that only a fraction states or goals were present during training. See Appendix for details.
conduct
of transitions
4-Room (Asym)
4-Room (Sym)
(Asym)
Maze (Sym)
1.0
0.8
Tox SRL
0.6
0.4
0.2
0.0
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.75 Training (goal)
0.50
1.00
Training (goal)
Training (goal)
Training (goal)
ouclidean
mlp
-
Ionn
+
deepnorm asym
widenorm asym
oreepoomm sym
widenorm sym
Fig. 5: GVF results. Generalization measured by SPL metric (higher is better) on held out (s, g) pairs as function fraction goals seen during training. Results averaged over 3 seeds and error bar indicates standard deviation. For fraction = we evaluate on entire data.
7

---

Published as a conference paper at ICLR 2020
Figure 5 summarizes the final generalization performance (on held out (s,9) pairs) for each archi- tecture after training for 1000 epochs. Performance is given in terms of the SPL metric (Anderson et al. 2018), which measures the success rate of reaching the goal weighted by the ratio of agent versus optimal path cost. We observe that when given only partial training data, Deep Norm and Wide Norm consistently outperform both MLPs and ICNNS each sparsity level. As expected, the Euclidean metric could not solve the asymmetric environments. Qualitatively, we plot a heatmap of the squared difference (SE) between the learned and ground truth value function in Figure (center), and observed that our proposed architectures have mostly lower SE than the MLP and ICNN architectures. Figure 4 (right) illustrates that WideNorm architecture is able to reach more cells (with almost optimal trajectory) in the environment when using a greedy policy with respect to the learned value function. Additional visualizations and results are in Appendix R2
3.5
COMPUTATIONAL CONSIDERATIONS
Several deep metric learning algorithms, such semi- hard triplet mining |Schroff' et al. (2015). involve computing a pairwise distance matrix for large mini- batches. For example, Schroff' et al. use mini-batches of size 1800. Computing this matrix for Euclidean distances can be done efficiently by taking advantage of the identity || 2122 |x|| + 11yll1 2x R.TTy y (see Section 4 of Oh Song et al. (2016) for details). This
32
128
512
2048
Euclidean
0.18
0.27
0.45
1.06
WN 3x600
1.59
1.57
1.75
2.36
WN 64x64
13.7
13.4
17.7
26.3
DN 2x400
0.97
5.73
76.9
293
DN 3x600
1.50
11.4
174
0OM
Fig. 6: Mean computation time (ms) for different mini-batch sizes (250 trials).
same identity can applied to each component of a Wide Norm. There is no obvious way, however, to compute pairwise Deep Norms more efficiently than the naive O approach. To quamtify, we recorded the pairwise distance computation time for our implementations (Table 6).. Thus, although our previous experiments often found that Deep Norms performed slightly better (see, e.g., Figure 3 and Tables PanlesPand] and 3b). these results suggest that only Wide Norms are practical for large mini-batches.
4 DISCUSSION AND OTHER RELATED WORK
Deep Norms, Wide Norms, and Neural Metries all respect the triangle inequality while universally approximating finite-dimensional asymmetric semi-norms. This allows them to represent metrics that the deep Fuclidean Siamese architecture cannot, no matter how deep its embedding function (see Figure 1. Our models thus provide more expressive, non-Euclidean alternative for learning distances that satisfy the triangle inequality. As noted in the Introduction, this may useful for providing running time and error rate guarantees in clustering (Davidson and Ravi 2009) and as an inductive bias to improve generalization performance (Figure Hsieh et al. (2017)
A line of theoretical work, surveyed by Indyk et al. (2017), characterizes the representational capacity of Euclidean space (and, more generally, lp space) by examining the asymptotic "distortion" "
of embedding n-point metric spaces into Fuclidean space. Here the distortion of embedding Φ : X' -> X" of metric space (X,dx) dx) into metric space (X",dx) ) is at most c 2 1 if there exists r 0 such that for all x, y X, r dx y) S (ó(x), oly)) S cr dy(x, y). The pioneering work of Bourgain (1985) bounds worst case distortion by O(log n). and Linial et al. (1995) shows that this bound tight (i.e., (llog for graph distances in n-point constant-degree expanders. This applies regardless of the dimensionality of the embedding space, and is true for all Ep with 1 < < 0o. Future work might investigate the asymptotic distortion of our proposed architectures.
On account of the above limitations. others have also proposed non-Eucke -on-Euciddean alternatives to learning and representing metrics. To improve expressivity, some have proposed -or-maraetrric algorithms that learn distances directly. For instance, Biswas and Jacobs (2015) propose to frame clustering as a metric nearness problem and applying a quadratic programming algorithm; see also Gilbert and Jain (2017) and Veldt et al. (2018). Others learn parametric distances, as we do. Bi et al. (2015) parameterize and learn Cayley-Kler metrics, which are not mansslatioo-ivvriinnn
Yang and Jin (2006) and Nielsen et al. (2016) propose metrics that are similar to our Wide Norm, in that they use non-negative sums of several components (binary codes and Cayley- -lein metrics). As for symmetry. several papers have used asymmetric measures such as KI. divergence (Vilnis and McCallum 2014
8

---

Published as a conference paper at ICLR 2020
Vendrov et al. 2013 Chen et al. 2016; Ou et al. 2016). To our knowledge, the first to propose a parametric measure that both asymmetric and satisfies the triangle inequality.
Another common approach in deep "metric" learning is forgo the triangle inequality altogether and use non-metric similarity measures such as cosine similarity (Bromley et al. 1994; Yi et al. 2014). This can be sensible, proper metrics not always required. In image recognition, for example, the triangle inequality is questionable: why should d(CAT, WOLF) - d(CAT, DOG) + d(DoG, WOLF)? In this case. |cheirer al. (2014) find that non-metrie similarities often perform better, concluding that "good recognition is non-metric". Thus, one should apply our models with care, in settings where the triangle inequality is thought be useful inductive bias (e.g., Hsich al. (2017)) Such applications we are excited about include learning search heuristics (Russell and Norvig] 2016) and scaling our UVFA models to more complex reinforcement learning problems (Plappert et al. 2018).
5 CONCLUSION
This paper proposed three novel architectures for modeling asymmetric They can be used instead of the usual Euclidean metric increase expressiveness while respecting the triangle inequality. We showed that our models outperform Euclidean metrics when used with Siamese-style deep metric learning architecture to (1) solve the metric nearness problem, (2) model shortest path lengths, and (3) learn general value functions in small reinforcement learning domains. Future work should explore larger scale applications such as facial recognition (Schroff et al. 2015). collaborative metric learning (Hsieh et al. 2017) and continuous control (Plappert et al. 2018).
and metrics.
ACKNOWLEDGMENT
We thank Cem Anil, James Lucas, Mitchell Stem, Michael Zhang and the anonymous reviewers for helpful discussions. Harris Chan was supported by an NSERC CGS-M award. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute (www. www.veeetorinstitueee.. #partners).
REFERENCES
Brandon Amos, Lei Xu, and J. Zico Kolter. Input convex neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 146-155, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http::/procceedirgg////////
press/v70/ http://000ammsl777 amosl7m html
Peter Anderson, Angel Chang. Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, et al. On evaluation of embodied navigation agents. arXiv preprint arXiv: 2018.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz. function approximation. arXiv preprint arXiv:1811.05530 2018
F. L. Bauer, J. Stoer, and C. Witzgall. Absolute and monotonic norms. Numerische Mathematik, 3(1): 257-264, Dee 1961. ISSN 0945-3245. doi: 10.10/F/00108002 URLhtttps://ooi.oo 10. 10.1007/5F01188 386026
Yanhong Bi, Bin Fan, and Fuchao Wu. Beyond mahalanobis metric: cayley-klein metric learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2339-2347, 2015.
Arijit Biswas and David W Jacobs. An efficient algorithm for learning distances that obey the triangle inequality. In BMVC, pages 10-1, 2015.
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):4655) 1985.

---

Published as a conference paper at ICLR 2020
Justin Brickell, Inderjit S Dhillon, Suvrit Sra, and Joel A Tropp. The metric nearness problem. SIAM Journal on Matrix Analysis and Applications, 30(1):375 396, 2008.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" stamese" time delay neural network. In Advances in neural information processing systems, pages 737-744, 1994.
Ying-Cong Chen, Wei-Shi Zheng, Jian-Huame Lai, and Pong Yuen. An asymmetric distance model for cross-view feature mapping in person reidentification. IEEE transactions circuits and systems for video technology, 1768:1661111755 2016.
Yize Chen, Yuanyuan Shi, and Baosen Zhang. Optimal control via neural networks: A convex approach. arXiv preprint arXiv: /805. 1835, 2018.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions information theory, 13(1):21-27, 1967.
lan Davidson and Sekharipuram S Ravi. Using instance-level constraints in agglomerative hicrarchical clustering: theoretical and empirical results. Data mining and knowledge discovery, 18(2):257-282) 2009.
Jozef Doboš. Metric preserving functions. Štroffikk Košice, 1998.
A. C. Gilbert and L. Jain. it ain't broke, don't it: Sparse metric repair. arXiv e-prints, October 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855 864. ACM, 2016.
Frank S He, Yang Liu, Alexander G Schwing, and Jian Peng. Learning to play in day: Faster deep reinforcement learning by optimality tightening. arXiv preprint arXiv: lew1.6111.166 2016.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In Aasa Feragen, Marcello Pelillo, and Marco Loog, editors, memilarity-Basser Pattern Recognition, pages 84-92, Cham, 2015. Springer International Publishing.
Cheng-Kan Kang Hsieh, Longqi Yang. Yin Cui, Tsung-Yi Yi Lin, Serge Belongie, and Deborah Estrin. Collaborative metric learning. In Proceedings of the 26th International Conference World Wide Web, pages 193-201. International World Wide Web Conferences Steering Committee, 2017.
Piotr Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the Thirty- first Annual ACM Symposium Theory of Computing, STOC '99, pages 428 434, New York, doi: 10. 10.1145/301250.301366 URL http1
NY, USA, 1999. ACM. ISBN 1-58113-067-8
7/doi acm. wtt.:////...111111111111 301366
Piotr Indyk, Ji''1 Matoušek, and Anastasios Sidiropoulos. 8: Low-distortion embeddings of finite
metric spaces. In Handbook of discrete and computational geometry, pages 211-231 Chapman
and Hall/CRC, 2017.
Eric Jones, Travis Oliphant, Pearu Peterson, al. SciPy: Open source scientific tools for Python, 2001. URL/http: //wp:////ww//ww//./// www.w.ccip...o... orrg/ [Online; accessed <today>].
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 14Xiv:1412.6940 2014.
Brian Kulis al. Metric learning: A survey. Foundations and Trends in Machine Learning, 5(4): 287-364, 2013.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-22 1995.
Frank Nielsen, Boris Muzellec, and Richard Nock. Classification with mixtures of curved mahalanobis metrics. In Image Processing (ICIP), 2016 IEEE International Conference on, pages 241-245.
IEEE, 2016.
10

---

Published as a conference paper at ICLR 2020
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In Proceedings of the IEEE Conference on Computer Vision and Pattem Recognition, pages 4004-4012, 2016.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. pages 1105-1114. ACM, 2016.
Matthias Plappert, Marein Andrychowiez, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforcement learn- ing: Challenging roboties environments and request for research. arXiv preprint (aff:::800000000 2018.
Stuart J Russell and Peter Norvig. Artificial intelligence: modern approach. Malaysia; Pearson Education Limited,, 2016.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pages 1312-1320, 2015.
Walter Scheirer, Michael J Wilber, Michael Eekmann, and Terrance E. Boult. Good recognition is non-metric. Pattern Recognition, 47(8):2721-27311 2014.
Florian Schroff. Dmitry Kalenichenko. and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few- soo-shot learning. In Advances in Neural Information Processing Systems, pages 4077-4087, 2017.
Suvrit Sra, Joel Tropp, and Inderjit S Dhillon. Triangle fixing algorithms for the metric nearness problem. Advances in Neural Information Processing Systems, pages 361-368, 2005.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Pestems-Volurre 2, pages 761-768. International Foundation for Autonomous Agents and Multiagent Systems, 2011.
N. Veldt, D. Gleich, A. Wirth, and J. Saunderson. A Projection Method for Metric-Constrained Optimization. arXiv e-prints, June 2018.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-cmbeddings of images and language. arXiv preprint 151.:65/1 2015.
Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. arXiv preprint arXiv:1412.6623, 2014.
Qi Wang, Jia Wan, and Yuan Yuan. Deep metric learning for crowdedness regression. IEEE Transactions on Circuits and Systems for Video Technology, 28(10):2633-2643 2018
Eric Xing, Michael Jordan, Stuart Russell, and Andrew Ng. Distance metric learning with application clustering with ind-information. In Advances in neural information processing systems, pages 521-528, 2003.
Liu Yang and Rong Jin. Distance metric learning: A comprehensive survey. Michigan State Universiy, 2(2):4, 2006.
Dong Yi, Zhen Lei, Shengeai Liao, and Stan ZLi. Deep metric learning for person re-identification. In Pattern Recognition (ICPR), 2014 22nd International Conference on, pages 34-39. IEFE, 2014.
11

---

Published as a conference paper at ICLR 2020
A PROOFS
In this Appendix, we restate each proposition from the main text and provide a short proof.
Proposition ! All positive homogeneous convex functions are subadditive; i.e, CI A N2 = N3.
Proof. Putting a = 0.5 in the definition of C1 gives f 0.5y) S 0z5f(z) + 0.5f()) Applying N2 on the left and multiplying by 2 gives f( + y) S f(z) + f(y as desired.
Proposition 2
If is an asymmetric semi-norm, then ||=]|| = ||||| + || is semi-norm.
Proof. |||||| = ||||| + -x] -I1-=|l. so N4 is satisfied. N2-N3 and non-negativity are similarly trivial.
Proposition 3
If lla is an (asymmetric) semi-norm, || ll is a norm (e.g., || ll. = -| 1122. and
À >>0 0, then
b a ||0||| \||=>||b an (asymmetric)
Proof. This follows from the positive definiteness of A||a|| and the easily verified fact that non- negative weighted sums of semi-norms are semi-norms
If || is N5 (semi-) norm R then | |rclu(x -z)ll, where :: denotes Proposition 4
concalenation, is an asymmelric (semi-) norm on R
Proof. N1 and N2 are easily verified. To see that ||. is not necessarily symmetric, choose || || to be Mahalanobis norm parameterized by diagonal W with Wú (but NB that if is invariant to element-wise permutations, as are the Lp norms, || will be symmetric). For N3, we have:
|| llvl = ||rcl((x :: -x)]l |I + ||reluly
-v) --)))
2 |]relu(x :: - -r) + relu(y :: -3)
2 ||rel([ + - (z + v))l
|| + yl.
The first inequality holds because ||-|| is N3. The second holds because || N5, and we have either element-wise equality (when si, and sign(y:) agree) or domination (when they don't). 0
Proposition
5
The Mahalanobis norm with W DU, with D diagonal and U non-negative, is N5.
Proof. Let ||
be l12, and S S z===z+ e. We have:
Ww ||| Well 2 ((W))
>>W"W(x+
=w W. + zU' D DUe
|[
The first inequality is Cauchy-Schwarz. The second holds as all elements of x. U D DU, and e are non-negative.
Lemma [ (Semilattice Stone- Weierstrass (from below)). Let C. a set of continuous functions defined compact subset K of R." L be closed subset C, and f E C. (I) for every E K, there exists 9x E L such that 9x S and (z(x) = f(z), and (2) L closed under max (i.e., a, b E I. max(a, E T.), then 3h E I. with f h on K.
- for x K. The U, form an open cover of K, so there is a finite subcover {Ua, U Uz....., Un J. Let = max Jwas-- .rr.. ) E
Proof. Fix e 0 and consider the sets Un ly y
We have f - S g S f. and the result follows since L is closed. L.
Theorem (UA for MICNNs). The family M of Max Input Convex Neural Networks (MICNNs) that uses pairwise max-pooling (or MaxRel.U) activations is dense in the family C of convex functions.
12

---

Published as a conference paper at ICLR 2020
Proof. For C, R", let Is M be a linear function whose hyperplane in the graph of is tangent to f at z. Then IN satisfies condition (1) of Lemma [ (because f is convex). The use of pairwise max activations allows one to construct max , h2) E MM for any two h1, h2 E M by
using log2 (n) max-pooling layers, satisfying condition (2) of Lemma]) 1 Thus f is in the closure of M, and the result follows.
L
Theorem 2 (UA for Deep Norms and Wide Norms). The families 'D of Deep Norms (using MaxRel.U) and W of Wide Norms (using MaxMean) are dense in the family N of asymmetric semi-norms.
Proof. The proof is almost identical to that of Theorem I The only subtlety is that D and W do not contain all linear functions in IR" they do, however, contain all linear functions whose hyperplane is tangent to any f E N, since f is N2. This is easy to see for functions defined on IR2. To generalize the intuition to R", consider the ray Rs {(axr :: a |a]l]) o 0} C R=+11 defined for each x E R". By N2, this ray is subset of the graph 9 C IR*+1 of f. Furthermore, any hyperplane tangent to one point on this ray tangent to the entire ray and contains all points on the ray, since the ray is linear from the origin therefore the hyperplane contains the origin. But any hyperplane tangent to g at is tangent to a point (x:) on the ray Rg. and so contains the origin. Since DD and W contain all linear functions containing the origin, it follows that they contain all linear functions whose graph is tangent to f. in satisfaction of condition (1) of [ (because ( f is convex). For Deep Norms, the use of pairwise max activations allows one to construct global max operation,
in the proof of Theorem I satisfying condition (2) of Lemma] T Wide Norms using MaxMean have direct access to a global max, and satisfy condition (2) of Lemma It follows that f is in the closures of D and W. D
The set of all asymmetric norms on R" is in one-to-one correspondence with the set of all bounded and open convex sets ("unit balls" ") containing the origin.
Proposition 6
Proof. Given asymmetric norm || on R", its unit ball B = | < 1] is convex since,
Vx, B À E 10, we have [[(1 - ))x + Xyll S (1 X)||=|| Allyll < (using N3 & N2).
Conversely, given open and bounded convex set B1 containing the origin, let || = inf > 0 _ e
B1}. N1 and N2 are straightforward and N3 follows by noting that for 2, y E R", a, > 0, such
that at $ B1, we have a
z+4 a+B
E BI, so that inf > aty B1 S inf
a+3
a+3
E B1} + in 0
B1).
Proposition 7 Metrricpreservvig concave functions). If d: X X - R+ is (quasi-) metric, (0) {0), and f is concave (i.e., ff convex), then ff d (quasi-) metric.
f: R
Proof. This proposition is proven for metries by Dobos 1998) (Chapter 1, Theorem 3). The extension to quasi metrrcs is immediate, as the proof does not require symmetry.
Proposition g (Max preserves metrics). If dj and d2 are (quasi-) metric, so too is max(d1, d2).
Proof. M1 and M2 are trivial. For M3, let d max (d,, d2). Given some x, y. 2, have both di(x, +d (y, =) 2 di (x, 2) and d2(x, +)+ =) 2 d2(2, =), so that d(x,, y)+d(y, 2) 2 di (x, z) and d(æ, y) d(w,,) =) 2 (3r, Therefore, d(x; y) + d(y, z) max(di (Iz, 2), da ()) dl (z, 2). Because if an element is larger than two other elements, it is also larger than their max.
Erratum dated July 6, 2020 The originally published version of our paper did not cite the prior universal approximation result for ICNNs by [Chn et al. (2018), which we were not aware of at the time. The text of Subsection 2.4/has been revised to reflect this prior work.
B IMPLEMENTATION DETAILS
Except where otherwise noted, these implementation details are common throughout our experiments.
Our Deep Norm implementation constrains each W, for i < k to be non-negative by clipping the parameter matrix after each gradient update. For WR, we use either a simple mean or MaxMean (see Subsection 2.3 We set Us O. We use either ReL.U or MaxReI.U for our activations Gt, as noted.
13

---

Published as a conference paper at ICLR 2020
Since the output layer is always scalar (size 1), we refer to Deep Norms in terms of their hidden layers only. Thus, a Deep Norm with & = 3 layers of sizes (400, 400, 1) is a "2x400" Deep Norm.
Our Wide Norm implementation avoids parameterizing the a; in Equation by absorbing them into the weight matrices, so that | = >; ||U,0|12, where U, = a,kW, Our asymmetric Wide Norm constrains matrix U of Proposition by clipping negative values and does not matrix D (i.e., set D I).
Neither our Deep Norm nor Wide Norm implementations impose positive definiteness. This simplifies our architectures, does not sacrifice representational power, and allows them to be used on pseudo- metric problems (where d(xr, y) 0 is possible for distinct x. y E X).
Neural Metrics involve only a very small modification to Deep Norms and Wide Norms: before applying the mean or MaxMean global activation obtain the final output, we apply an element-wise concave actívation function, as described in Subsection 3.1
C 2D NORMS ADDITIONAL DETAILS
Dataset generation To generate data, we use Proposition by generating random point set, computing its convex hull, and using the hull as the unit ball of the generated norm, || Having obtained the unit ball for random norm, we sample a set of N 500 unit vectors in R22 (according to I2) in random directions, then scale the vectors until they intersect the convex hull: {x) We use these vectors for testing data, defined as Drest = {xx(),, 1).... 1)). For training data, we sample a size D = {16, 128) subset of these vectors and multiply them by random
perturbations (i)) (0.855, 1.15) to get (& [&(+) = =+) The training data is then defined as Dirain {(+11) ()),..., (a(R), ).
Models We compare 4 model types on 4 types norms. The models are (1) Mahalanobis, (2) Deep Norms of depth E {2, 3, 5) and layer size E {10, 50, 250), (3) Wide Norms of width E {2, 10, 50] and number of components E {2, 10, 50), and (4) unconstrained. fully connected neural networks with ReLU activations of depth E {2, 3, 4, 5, and layer size E {10, 50, 250} (MLPs). Although MLPs do not generally satisfy N1-N4, we are interested in how they generalize without the architectural inductive bias.
The norms experiment are random (1) symmetric and (2) asymmetric norms, con- structed as above, and (3) square (Lo,), and (4) diamond (Lz) norms.
Norms
Training The models, parameterized by 8, are trained to minimize the mean squared error (MSE) between the predicted (scalar) norm value [| and the label norm value (9); L())
1 >> (I|=011e (0),, where M = 16 is the batch size. We use Adam Optimizer Kingma and Ba 1, 2014), with learning rate 1e 33, and train for maximum of 5000 epochs.
Results Tables 7 show the test MSE for the best configurations for each target norm and training data size. Deep Norms performed orders of magnitude better than Mahalanobis and Wide Norms on the random symmetric and asymmetric norms, but Wide Norms performed better on the square and diamond norms. The MLP performed worse than our models, except on the asymmetric norm with small training data.
Figure Jillustrates the learned norm balls for random symmetric and asymmetric norms, when trained with small (A: 16) and large (A: 128) data sizes. Appendix SoandixCCinnlune Ciiclldes additional visualizations. From the red contours, we observe that Deep Norms and Wide Norms generalize to larger and smaller norm balls (due to being N2), whereas the MLP is unable to generalize to the 0.5 norm ball.
C.1 ADDITIONAL DETAILS ON NORM GENERATION
To generate point sets in ? we generated c E [3. 10] clusters, each with n; E [5, 50) random points. The points for each cluster were sampled from truncated normal distribution with μº u((005 0.5) and d4i) (1(222 0.6), truncated to 2 standard deviations. For symmetric sets, considered only
14

---

Published as a conference paper at ICLR 2020
Maha
DN
WN
MLP
sym
16
10
1.5x10
6.7x10-5
155
128
3.2x 10
7.8x10
10010
122x10
asym
16
107
4.1x10-4
4.9x 10 4.5x10-3
16x10-3
128
1.7x10-1
2.5x10-
3.0x
square
16
107
3.0x10-8
2.4x 10
7.7 x.7x10-3 7.8x10-6
128
101x10-2
2.1x10-0
9.3x 10
di aimon
16
1.2x 10
6.5 10
x.6x
2.2x 10 7.8x
128
1.1x10-2
4.5x10-7
2.3x
Table 5: MSE on 2d norm test set (target value 1) for the best configuration of each type (allowing for early stopping), for each data size (16 and 128) and target norm.
Maha
DN
WN
MLP
sym
16
1 1.3x 10
6.0x10-8 3.1x10-6
2.7x
3.8x 30-2 20
128
1.0x10-6
asym
16
60-
1.6x10--
2.0x
200x10-1
128
607x10-1
2.0x10-*
18810
288x00-2
square
16
6.8x
1.2x
9.6x10
2.7
128
40
8.3x 10-6
307x10-=
6.1x10
diamond
16
10 4.4 10
2.6x 10
1.9x10-7
4.1x10-1 704
128
1.8x 10-6
9.3 x 10
Table 6: MSE on 2d norm test set (target norm value 2) for the best configuration of each type (allowing for early stopping), for each data size (16 and 128) and target norm.
Maha
DN
WN
MLP
sym
16
8.5 10
3.7x10-1
10-
40- 1--
128
8.1x 10
2.0x10-7
2.5x
asym
16
4.2x10
1.0
1.2x 10
7.9x
128
1
6.2x10-
11
-0
square
16
4.3x
7.5x 10-
6.0x10-1
7-5
128
2.7x10
5.2x10-7
2.3x 10
100
diamond
16
2.9 10
1.x 10
1.2x10-5
10
128
2.8 10
11
5.8x10 11
10
Table 7: MSE on 2d norm test set (target norm value = 0.5) for the best configuration of each type (allowing for early stopping), for each data size (16 and 128) and target norm.
15

---

Published as a conference paper at ICLR 2020
those points with positive z-coordinates and also included their reflection about the origin. To ensure that the origin was inside the resulting convex hull, we normalized the points to have mean zero before computing the hull. The convex hull was generated by using the SciPy library Jones et al. (2001) ConvexHul] implementation.
C.2 ADDITIONAL VISUALIZATIONS
Figure 8 and Figure 7 fürther visualizes the training data and Mahalanobis architecture in addition to the MLP. Deep Norm, and Wide Norm architectures, for the random symmetric, asymmetric, square (o) and the diamond (L1) unit ball shape.
Training Data
Mahalanobis
Deep Norm
Wide Norm
MLP
40
-35
1,000
L00
13
1500
25
-15
(a) Small Dataset (k 16)
Training Data
Mahalanobis
Deep Norm
Wide Norm
MLP
1.2
134
-0.
-12
20
12-
20
-63
-32
(b) Large Datasct (k 128)
Fig. 7: Visualization of the 2d unit circles learned by several architectures (see Section 2.5 for square and diamond shape convex hull, corresponding to Loo and L1 norm unit circle, respectively. The first column shows the training data points (in green), while the red line the convex hull illustrates the portion of the convex hull which is covered by the training vector. Blue contours represent ground truth norm balls, and red contours learned norm balls, in each case for norm values (0.5, 1,
16

---

Published as a conference paper at ICLR 2020
Training Data
Mahalanobis
Deep Norm
Wide Norm
MLP
JaK.
35
63-
-03
25
12-
-1.4-
-3.
10
(a) Small Dataset (A 16)
14-
Training
Deep
40
2000
142
-1.
15
63
-03
45
-2
(b) Large Dataset (A 128)
Fig. 8: Visualization of the 2d unit circles learned by several architectures (see Section 2.5) for symmetric and asymmetric shape convex hull, corresponding Lo and L1 norm unit circle, respectively. The first column shows the training data points (in green), while the red line to the convex hull illustrates the portion of the convex hull which is covered by the training vector. Blue contours represent ground truth norm balls, and red contours learned norm balls, in each case for norm values {0.5, 1,2].
17

---

Published as a conference paper at ICLR 2020
D METRIC NEARNESS ADDITIONAL DETAILS
Dataset creation For the symmetric metric nearness dataset, generated the data as found in Sra et al. (2005): a random matrix in IR 20000 was generated with values drawn from the uniform distribution ranging between 0 and 5. This matrix added to its transpose to make it symmetric. Random uniform noise was added to each entry between O and 1, then the diagonal was removed. For the asymmetric case, a random asymmetric matrix generated as above was too difficult task for triangle fixing. Instead, we generated a random directed lattice graph with random weights generated from the exponential function applied to a random uniform sample between -1 and 1. The distances were calculated using Dijkstra's 's A algorithm. Then, again, random uniform noise between 0 and was added the output, multiples of 10 removed to make the scale comparable to before, and the diagonals removed. The reason for the extra noise was due to the fact that the data matrix was already much closer to metric.
complex dataset creation strategy was employed due the fact that
Architectures used For the symmetric metric nearness experiment, the Deep Norm based Neural Metric architecture used two layers of 512 neurons (we found that larger layer sizes learned much faster), with a 512-dimensional embedding function, MaxReLU activations, 5-unit concave activation functions, and a MaxMean global pooling layer. The Wide Norm based Neural Metric consisted of 128 Mahalanobis components of size 48, with 51 512-dimensional embedding function, 5-unit concave activation functions, and MaxMean global pooling. The deep Euclidean architecture used 1024-dimensional embedding function. For the asymmetric case, the architectures were the same except that we used the asymmetric equivalents for Deep Norm and Wide Norm.
Training Regime The triangle fixing algorithm was allowed to go up to 400 iterations or conver- gence. For the symmetric case we reimplemented Sra et al. (2005) Python using their C++ code as template. For the asymmetric version, we used the same code but we removed their symmetrization step. For the training of all networks, we did 1500 epochs total split up in to 500 epoch chunks were the learning rate decreased from 1e-3 to 3e-4 to le-4 at the end, using batch size of 1000.
We used the Adam optimizer Kingma and Ba (0014) with default hyperparameters. Results were averaged over 10 seeds.
Backsea
Deep Norm viide korm
0.4
0.
022
0.0
620
1130
Fig. 9: Learning curves on symmetric metric nearness.
E GRAPH EXPERIMENTS ADDITIONAL DETAILS
Symmetric graph descriptions The first symmetric graph, to, consists of a symmetrized road network extracted from openStreetMap (OSM, www.openstreetmap.og) The second, 3d, represents navigation a 50x50x50 cubic 3d gridworld, where the agent can move one step at a time directions, and movement wraps around the sides of the cube. The third, taxi, represents 25x25 2d taxi environment, where the agent can move in four directions and there is a passenger that the agent can pick up and drop. Unlike in 3d, there is wraparound in taxi. Weights for edges in to correspond to the OSM distances, whereas weights for edges in 3d and taxi are randomly sampled from (0.01, 0.02, ..., 1.00} (but final distances are normalized so that the mean distance is 50).
18

---

Published as a conference paper at ICLR 2020
Asymmetric graph descriptions The first, push, is a 25x25 2d pusher environment, where the agent can move in four directions, and there is a box that the agent can push by moving into it. If the box is pushed into wall, it switches places with the agent. The second, 3dd, is a directed version of 3d, where all paths in three of the six movement directions have been pruned (the same three directions for all nodes). The third, 3dr, is randomly pruned version of 3d, where three random movement directions were pruned at each node, and any inaccessible portions of the resulting graph were pruned.
Dataset generation Our experiments are structured as a supervised learning task, with inputs F, E V and targets d(z, y). The targets for a random subset of 150K pairs (of the ((IV))
total pairs) were computed beforehand using A search and normalized to have mean 50. 10K were used as a test set, and the remainder was subsampled to form training sets of size |D] E {IK, 2K, 5K, 10K, 20K, 50KJ. Nodes were represented using noisy landmark embeddings. A subset of 32 landmark nodes was randomly chosen, and the distances to and from all other nodes in the graph were computed using Dijkstra'ss algorithm to form 32 base landmark features for symmetric graphs and 32 base landmark features for asymmetric graphs. These base landmark features were then normalized to have mean O and standard deviation 1, and noise sampled from ( 0.2) was added. To add additional noise through distractor features, 96 normally distributed features were concatenated with the noisy landmark features obtain node embeddings with 128 dimensions for symmetric graphs and 160 dimensions for asymmetric graphs. We also tested node2vec embeddings Grover and Leskovee (0116). but found that our noisy landmark approach was both faster to run and produced results that were an order of magnitude better for all algorithms.
Architectures We compare 128- dimensional Mahalanobis metric (equivalent to deep Euclidean metric with an additional layer), Wide Norm based Neural Metric (32 components of 32 units, with 5-unit concave activations, and MaxMean global pooling), plain Deep Norm (3 layers of 128 units, ICNN style with ReLU activations, no concave activations, and average pooling, DN,), and a Deep Norm based Neural Metric (3 layers of 128 units, with MaxReLU and 5-unit concave activations, and MaxMean pooling, DN and an MLP (3 layers of 128 units). We train each algorithm with 4 different embedding functions ø each a fully connected, fced-forward neural network with ReLU activations. The depths of tested á ranged from 0 to 3 layers, all with 128 units. No regularization was used besides the size/depth of the layers.
Training Training was done end-to-end with Adam Optimizer Kingma and Ba 2014). using an initial learning rate of le-3 and a batch size of 256. Networks were each trained for 1000 total epochs, and the learning rate was divided by 5 every 250 epochs.
Results
The complete results/learning curves are displayed in Figures 10 and below.
F GENERAL VALUE FUNCTIONS ADDITIONAL DETAILS
F.1 EXPERIMENTAL DETAILS
4- 4-Room and Maze environment description The fully observable grid environment has state and goal representation represented by a 1-hot vector with 3 dimensions, indicating whether the cell is (I) empty, (2) wall, (3) agent. The agent can move up to 4 cardinal directions (North, South, East, West). If wall is present in the direction then the agent cannot take that move. The 4-Room environment and Maze environment has a total of 4556 and 2450 training (s.g) pairs, respectively. For each environment, the agent has access to neighbour function (ss) which returns a list of possible next states, corresponding to the empty cells adjacent to the current agent location. This is equivalent to having environment transition model p(s'|s, (1s00 a) over all the actions.
binary tensor with dimensions 11 x 11 x 3. Each cell in the 2D grid
Transition reward and episode termination For symmetric environments, every transition has reward of ie., R's, = -1. Note that reward is not a function of the goal, but the termination is. For asymmetric environments, if the direction of movement is west (left) or south (down). The done flag is set to when the neighbouring state equals to the goal, i.e. D(s, s'g) ss' = g).
add noise μ ~ 21(0. -5) to the base -1 1 reward for transition
19

---

Published as a conference paper at ICLR 2020
Choosing Training-Test Split Dataset Given the full training data set of (s.g) pairs, use types of splitting into train and test datasets: (1) goal, and (2) state. We denote the training fraction 7 = [0,1] as the fraction of the total data points used for the training set. For goal splitting,
pick
a subset of goals {g"}. S ! with Kg H| R (1 r)) (g)) and remove all (s, g) pairs where E g", These goals were chosen to be the percentage of empty cells from the bottom from the training
of the grid, when numbering the empty cells from left to right, and top-down (i.e. reading order of words a page). This corresponds to approximately fraction of the bottom rows goals. this case, the training set observes all possible states, and hence also all the transition rewards. We are interested in whether it can generalize to new unseen goals. For state splitting, we perform a similar procedure but instead with subset of states which are removed, with the states corresponding to the agent being at the bottom rows of the grid. While all the goals are included in the training dataset, in the state splitting, some states and transition rewards are unknown to the agent, hence much more difficult to generalize.
The architectures used for the experiments consist of shared feature extractor ø for the state and goal g, followed by a function fe on the difference of the features:
Architecture
V(s. o, 0) fo(((9) <(s))
(4)
The feature extractor é is composed convolutional layers with 3 kernel size, and 32 and 62 filters with ReLU activations and stride of 1. We then flatten the feature maps and follow by fully connected layers of hidden size 128 and 64, with ReLU activation on the first layer only. The variants of fe are summarized in table 8 Euclidean simply computes the L2 norm between the feature embeddings: [[Ø(g) (())]l2:
Table 8: Value Function Architectures
# Hiddens
# /Components
Layers
Act. Func.
Concave Units
Pool Func.
/Component
Size
MLP
64
3
ReLU ReLU
ICNN
64
3
DeepNorm
64
3
MaxReLU
5
Mean
WideNorm
64
32
5
Mean
Training L( 0):
The objective function for training the models is the Temporal Difference (TD) Error
[(6 = D -1
(5)
(r(s,''g)) g) max V ... 0,0,), if +g y (r(s,''
(6)
otherwise
Where N(s) refers the set of next states of after applying different actions that state. Note that we did not apply discount factor on the value of the next state (i.e. the discount factor 1). We make use of target networks 5, 0 when computing the target y. The target networks are updated once every epoch of training, via exponential moving average (Polyak Averaging) with the main networks (Ø, 8):
((++1) = (n) (1 a))))))
where, a = 0.95 is the update fraction. We use Adam Kingma and Ba (2014) with learning rate 0.0001, batch size 128, for 1000 epoch. We evaluate SPL metric every 200 epoch.
20

---

Published as a conference paper at ICLR 2020
Evaluation Metrics We evaluate the learned value functions several metrics: MSE, Policy Success, and Anderson et al. (2018). The MSE was calculated on on the ground truth value of the held out test set V(s.g). For policy success and SPL, we select N 100 random (s, g) pairs in the test set, initialize the agent at 8, and follow a greedy policy to visit the neighbour arg max', r(s, 8¹) V(s') for up 7 121 timesteps (11 11). If the agent reaches the desired goal within the episode then the binary success indicator S; = 1 and the episode terminates, and 0 otherwise. Let 4 be the ground truth (ss.g) g) optimal episode cumulative reward (i.e. path cost), and the cumulative reward in the episode by the agent's 's trajectory. We then define the Policy Success rate and SPL as:
1
N
1 SPL
N
4 max ps: 4)
Success
S
S
(8)
N
N
1m1
F.2 ADDITIONAL EVALUATIONS AND VISUALIZATIONS
We visualize additional heatmaps for (1) learned value function (Figure 15 (2) Squared Error (SE) between the ground truth value and the learned value (Figure [6), and (3) SPL metric for individual (so. 8) and (s, so) pairs (Figure 17). These results are for agents trained with training fraction 1 0.75.
In comparing the performance versus training fraction, we also plot the final performance after 1000 epoch of training: (1) training set SPL versus training fraction (Figure [ap. (2) Train (Figure [4a] and test (Figure 14b) mean squared error (MSE) with the groundtruth values. We note that while our Deep Norm and Wide Norm appears to have higher MSE than the baselines, in practice when utilizing the value function with greedy policy, our architectures were able to achieve better success than the baseline architectures.
21

---

Published as a conference paper at ICLR 2020
[D]
1000
[D]
2000
55000
[D| 10000
20000
[D] 50000
MLF MSSE DN-12 (MSE) WIN (MSH) Maha (MSE)
18
min to 23
Final 28
final 51
te
finall 15
final
Sinal to
11
tr
26
16
mito te 24 Firal ao 17
zin to Millnn li
12
final to 17
min to 10
mine to finill 13
Tinar
miln 0
min to 2
10
26
min molllae te 55
min final to 13
min
Eicin te 15
finil tu 17
final 9
Final be 7
16
min to 37
min
min ta
min ta 10
with 9
final
min to 2
500
1000
503
1000
500
1000
500
1000
500
1000
500
1000
(a) Learning curves for to
[D] = 1000
[D] = 2000
5000
[D]
10000
[D] = 20000
[D] = 50000
Maha (MSE)
40
30
1e
20
10
min te:3 Finul to 30
Final 29
min 27
final
min to 24
final to 25
min to 23
+tnot to 33
nin 23
finall tc
min te 21
WN (MSE)
18
10
Final to 48
Final te
final to 36
final to 47
final in 54
final tn 37
MLP (MSE) DN-NM (MSE)
46
-6
16
min to 37
nin to 21 Finel 20
mire to 26
min to 25
finel E2
mike tu 22
moire te 22
18
17
1r
te
16
min
mia 25
Rinol to 42
final 36
final te 39
final to 41
finall 30
final ke 21
1000
500
1000
500
1000
1000
500
1000
500
1000
(b) Learning curves for 3d
[D] 1000
[D] 2000
5000
10000
20000
[D] 50000
Maha (MSE)
min 75 to
to final 29
Final
final to
final
final
10
WN (MSE)
16
to
20
to
min te 134
min te 07
min to 41 te
mie to 29
min 14
min to 20 finall
MLF MMSE) DN-NM (MSE)
30
U
30
16
min final to 24
Final be 52
final be 43
final ba 32
finall be 13
final to 31
88 18
min te 57
min
min to
min to 14
min 10
min te 5
500
1000
503
1000
500
1000
500
1000
0
500
1000
500
1000
(c) Learning curves for taxi
Fig. 10: Symmetric graph learning curves.
22

---

Published as a conference paper at ICLR 2020
[D]
1000
[D]
2000
-5000
[D| 10000
20000
[D] 50000
Maha (MSE)
20
23 final to
TinaTTe
Final
final to 25
finall
Final
MLP (MSE) DN-NM (MSE) WN (MSE)
16
40
t-
16
miin be 26 to 34
min te 31 Final
min te 20
min to 24 ninar
mile 23
min to 27
Tinal fo
26
16
minn
Final be 52
Final the 40
final Ia 30
final to 26
final the 23
Sinal In 38
1 8
15
min to 35
min
min to
min to 23
min 22
min to
500
1000
503
1000
500
1000
500
1000
500
1000
500
1000
(a) Learning curves for 3dr
[D] = 1000
[D] = 2000
DD|
5000
[D]
10000
[D] = 20000
[D] = 50000
Maha (MSE)
40
70
10
-0
10
min te 252
281
final 254
min 237
final to 240
min to 227
final to 230
min to 222
final 223
min 215
Final 232
min to 212
MLP (MSE) DN-NM (MSE) WN (MSE)
10
final to 231
final te 225
final te 214
final to 205
final to 193
final to 177
40
-6
1/
20
minn ta 251
min to 226
min to 225
min to 221
mis to 201
mis to 156
16
17
tr
ke
te
20
16
226
222
min 207
min 180
175
125
Final to 334
(lool 317
final te 31.0
final to 253
final 254
(Inol to 253
1000
500
1000
500
1000
1000
500
1000
500
1000
(b) Learning curves for 3dd
[D] 1000
[D] 2000
5000
10000
20000
[D] 50000
Maha (MSE)
min
to final 36
te
to 62
Final
final to 39
finall
final
40
MLP (MSE) DN-NM (MSE) WN (MSE)
16
20
10
min be 40
40
min be 21 Final
min te 24 final te
mie to 20 20
min 14 18
min to 24 finall
30
U
30
16
min final to 22
Final te 36
linal le 39
final be 26
finall be 20
final to 33
88 18
15
min to 47
min
min to
min to 18
min 34
min t. final
500
1000
503
1000
500
1000
500
1000
0
500
1000
500
1000
(c) Learnnng curves for push
Fig. 11: Asymmetric graph learning curves.
23

---

Published as a conference paper at ICLR 2020
4-Room Env
4- 4-Room Asym Reward
4-Room Asym Value
-5
220
-25
-30
Maze Asym Reward
Maze Asym Value
E
E3
-10
-20
-30
-50
-60
-70
Fig. 12: GVF environments. Left: The 4-Room and Maze environments, with walls (green), empty cells (red), and agent (blue). Center: Rewards in asymmetric environments. Symmetric versions have reward everywhere. Right: Example ground truth value, where state so denotes agent at top left cell. Upper triangular regions indicate the value of V s) while lower indicate (8, 80).
24

---

Published as a conference paper at ICLR 2020
4-Room (Asym)
4-Room (5ym)
Maze (Asym)
Maze (Sym)
1.00
Tran SPL
0.50
Training Frac (goal)
Training Frac (poal)
Training Frac (goal)
Training Frac (goal)
Train SM1
0.75
0.00
Training Frac (state)
Training Frad (state)
Training Fraz (state)
Training Frac (stote)
oudlidcan
mip
-+ Icnn
deepnorm asym
widenorm asym
deepnorm
widenorm sym
(a) Train Set SPL versus fraction of training set.
4-Room (Asym)
4-Room (Sym)
Maze (Asym)
Maze (Sym)
1.00
0.50
Training Frac (goal)
Training Frac (goal)
Training Frac (goal)
Training Frac (goal)
0.75
0.00
0.50 Training Frac (state)
Training Frac (state)
Training Froc (state)
Training Frac (state)
eudidean
mlp - Icnn
deepnorm asym
widenorm asym +
deepnorm sym
widenorm sym
(b) Test Set SPL versus fraction of training set.
Fig. 13: Additional performance on the train/test SPL metric vs training fraction for the four environment variants (higher is better).
25

---

Published as a conference paper at ICLR 2020
4-Room (Asym)
4-Room (5ym)
Maze (Asym)
Maze (Sym)
0.100
Train MSE
0.10
0.075
0.04
0.05
0.025
Training Frac (gpal)
Training Frac (goal)
Training Frac (goal)
Training Frac (goal)
0.100
Train MSE
0.04
0.04
0.075
0.07
0.050
0.02
0.05
0.025
0.00
0.00
0.000
0.00
Training Frac (state)
Training Frac (state)
Training Frac (state)
Training Frac (stato)
cuclidcan
mip
-
Innn
deepnorm asym
widenorm asym
deepnorm
widenorm sym
(a) Train Set MSE versus fraction of training set.
4-Room (Asym)
4-Room (Sym)
Maze (Asym)
Maze (Sym)
0.8
Test MSB
0.6
1.5
0.2
0.5
Training (goal)
Training Frac (goal)
Training Igoal)
Training Frac (geal)
300
800
400
Tost
600
200
100
200
Trai Frac (state)
Trairing Frac (state)
Training Frac (stabe)
Training Frac (state)
eudldden
mlp
-
Icnn
deepnorm asym
+ widenorm asym
deepnorm sym
widenorm sym
(b) Test Set MSE versus fraction of training set.
Fig. 14: Additional performance on the train/test MSE metric vs training fraction for the four environment variants (lower is better).
26

---

Published as a conference paper at ICLR 2020
VaLe Crandtoonn
Valu CH
VALLE Conattrr ACT
1I.E Coeptam
SHHors Aar
oa Wiuutory Sart
4 4-Room Asymmetric environment
Vale Crendroo
Yebs Beldee
VoLL
Vake CN
Value Cueator Nor
Wout Doeptam Syr
We Selors Aaw
We Weatory Ser
(b) 4 4-Room Symmetric environment
VALE SALESmantionn
Web Duldee
Vil MPP
Vaba CI
VALUE CsRator NEm
182t www.aammmmmm
Wa Selors Aar.
la Wealory Sart
(c) Maze Asymmetric environment
C
F
F
F
F
DALE MALEEAA
Vaka
Dwnteeeae Sye
don
F
FF
(d) Maze Symmetric environment
Fig. 15: Learned Value Function for the four environments with Train Fraction = 0.75.
27

---

Published as a conference paper at ICLR 2020
26 Caliier
2 PM
CAM
S4 DeIpHoTT Ap
Duesitorr Spn.
SE w.-.Hore d0y
Kalu Seoastrutt
4-Room Asymmetric environment
Vakce Croundacon
Sc Midlssmmmm Syn
Eatibee
ZENP
SEKIN
24 Dasstommnn Ay
2t W-Stlorr Apy
(b) 4-Room Symmetric environment
F
+
F
T
189
(c) Maze Asymmetric environment
Fr
(d) Maze Symmetric environment
Fig. 16: Squared Error (SE) compared the ground truth value function for the four environments with Train Fraction = 0.75.
28

---

Published as a conference paper at ICLR 2020
bxcloaar
NJP
KCW
Deestem Ady
SR Peepheen Sym
SPL Waleleem Alyen
VILY
Aam
SM Ceeptern Spm
Aoym
Widehorn
(a) 4 4-Room Asymmetric environment
bxcldeer
MJ
BeesHem
5Pt Pespher
SPL WhaWWhhemmmmn
440000 1e0
5P. Beclderr
37s NJ
57. Deszlem Apm
2/ Copphom 9mm
St Wese Apyn
Jobor on bec 2014
(b) 4-Room Symmetric environment
Dxcldeer
SU
SPLICW
Deszlern
SPL Ceupherm
Whaelbem
Budddar
SPUEON
Deeslem Apm.
SR Deepheen Sum
SPL WLWWirrtemmoo Asym
Widteen
(c) Maze Asymmetric environment
SUUNU
SELICN
Sym
SP. Bebieee
SPLENS
3P. Dew.tem Apm
SI DrpDppp Sm
SPL PPLWWe Avyn
Sasion THe
(d) Maze Symmetric environment
Fig. 17: Success weighted by Path Length (SPL) metric the four environments with Train Fraction 0.75.
29


Reviews:
[{"review_id": "r1lR8p5IqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nI 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. \n\nMy 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.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Ske1Vfqa9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HyxOWBlB9B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nThe 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.\n\nAfter 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.\n\nI 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. \n\nWe 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.\n\nFinally, 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.\n\nIn 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJgoBv0JcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows how to enforce and learn non-Euclidean\n(semi-)norms with neural networks.\nThis is a promising direction for the community as part\nof a larger direction of understanding how to do better\nmodeling in domains that naturally have non-Euclidean\ngeometries.\nThis paper shows convincing experiments for modeling\ngraph distances and in the multi-goal reinforcement\nlearning setting.\n\nOne clarification I would like is related to some\ntasks inherantly not having a Euclidean embedding.\nAre there works that theoretically/empirically characterize\nhow bad this assumption can be for some problem classes?\nEven though some tasks are impossible to embed exactly\ninto a Euclidean space, are there sometimes properties\nthat, given a high enough latent dimensionality,\nthey can be reasonably approximated?\nAnd in the table of Figure 1, whta dimension n was used\nfor the Euclidean norm?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)