Year: 2020

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 R, 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.1

heading: 1 INTRODUCTION
text: 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)—it 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 a 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 in deep metric learning (Yi et al., 2014; Hoffer and Ailon, 2015; Wang et al., 2018) is to use a Siamese network (Bromley et al., 1994) that computes a Euclidean distance in the latent space. Specifically, the Siamese network models distance dX : X × X → R+ on domain X by learning embedding φ : X → Rn and computing dX (x, y) as ‖φ(x)− φ(y)‖2. Successful applications include collaborative filtering (Hsieh et al., 2017), few-shot learning (Snell et 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-regular graphs), there is no embedding φ : X → Rn that can model dX precisely using ‖ · ‖2 (Indyk et al., 2017). A classic example is shown in Figure 1. In part due to these issues, some have considered non-architectural constraints. He et al. (2016) impose a triangle inequality constraint in RL via an online, algorithmic penalty. Implementing such a penalty can be expensive, and does not provide any guarantees. An approach that does guarantee
1Code available at https://github.com/spitis/deepnorms
Published as a conference paper at ICLR 2020
... ... ... ... ... ... Cleaned up version
Blah
Blah
Blah
Norm MSE
Euclidean, Rn, ∀n 0.057 Deep Norm, R2 0.000 Wide Norm, R2 0.000
Deep Norm Wide Norm Mahalanobis
1 0 11.5
1.0
0.5
0.0
0.5
1.0
1.5
A B
C D
1 0 1
1
0
1
A B
C D
1 0 1
1.0
0.5
0.0
0.5
1.0
A
B
C
D
Fig. 1: The nodes in the graph (left) cannot be embedded into any Rn so that edge distances are represented by the Euclidean metric: points φ(A) and φ(D) must lie at the midpoint of the segment from φ(B) to φ(C)—but then φ(A) and φ(D) coincide, which is incorrect. Our models fit the data in R2 (middle). The visualization (right) shows learned norm balls in red and embeddings in blue.
satisfaction of triangle inequality is to fix any violations after learning, as done by Brickell et 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 Euclidean distance?
In response to 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 metrics, (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., 2011). 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 or increase expressiveness.

heading: 2 MODELING NORMS

heading: 2.1 PRELIMINARIES
text: Our goal is to construct expressive models of metrics and quasi-metrics on domain X . A metric is a function d : X × X → R+ satisfying, ∀x, y, z ∈ X : M1 (Non-negativity). d(x, y) ≥ 0. M2 (Definiteness). d(x, y) = 0 ⇐⇒ x = y. M3 (Subadditivity). d(x, z) ≤ d(x, y) + d(y, z). M4 (Symmetry). d(x, y) = d(y, x).
Since we care mostly about the triangle inequality (M3), we relax other axioms and define a quasimetric as a function that is M1 and M3, but not necessarily M2 or M4. Given weighted graph G = (V, E) with non-negative weights, shortest path lengths define a quasi-metric between vertices. When X is a vector space (we assume over R), many common metrics, e.g., Euclidean and Manhattan distances, are induced by a norm. A norm is a function ‖·‖ : X → R satisfying, ∀x, y ∈ X , α ∈ R+: N1 (Pos. def.). ‖x‖ > 0, unless x = 0. N2 (Pos. homo.). α‖x‖ = ‖αx‖, for α ≥ 0. N3 (Subadditivity). ‖x+ y‖ ≤ ‖x‖+ ‖y‖ . N4 (Symmetry). ‖x‖ = ‖ –x‖.
An asymmetric norm is N1-N3, but not necessarily N4. An (asymmetric) semi-norm is nonnegative, 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) = ‖x − y‖, and first construct models of asymmetric semi-norms. Any induced quasi-metric d is translation invariant—d(x, y) = d(x+ z, y+ z)—and positive homogeneous—d(αx, αy) = αd(x, y) for α ≥ 0. If ‖ · ‖ is symmetric (N4), so is d (M4). If ‖ · ‖ is N1, d is M2. Metrics that are not translation invariant (e.g., Bi et al. (2015)) or positive homogeneous (e.g., our Neural Metrics in Section 3) cannot be induced by a norm.
A convex function f : X → R is a function satisfying C1: ∀x, y ∈ X , α ∈ [0, 1]: f(αx+(1−α)y) ≤ αf(x) + (1− α)f(y). The commonly used ReLU activation, relu(x) = max(0, x), is convex.

heading: 2.2 DEEP NORMS
text: It is easy to see that any N2 and N3 function is convex—thus, all asymmetric semi-norms are convex. This motivates modeling norms as constrained convex functions, using the following proposition. Proposition 1. All positive homogeneous convex functions are subadditive; i.e., C1 ∧ N2⇒ N3.
...
Less misleading:
The proof is straightforward (put α = 12 in C1 and apply N2 to the left side). To use Proposition 1, 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 is defined as:
for i = 1...k, where x is the input, h0 = 0,W+1 = 0, the activation functions gi preserve C1 and N2
(element-wise), gk is non-negative, W+i is a non-negative matrix, and Ui is an unconstrained matrix.
As compared to the original ICNN architecture, we have omitted the bias terms from Equation 1, have constrained the gi to preserve positive homogeneity while also allowing them to be any function that preserves element-wise convexity (this is essential to our universal approximation results), and have required gk to be non-negative. It is easy to verify that the set of valid element-wise gi is {gαβ(x) = α relu(x) + βx |α, β ≥ 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 on multiple inputs (and preserve element-wise C1 and N2). In particular, we use the pairwise MaxReLU:
maxrelu(x, y) = [max(x, y), α relu(x) + β relu(y)], where α, β ≥ 0 (2) Deep Norms are N2 and N3. Using the following propositions, we may also impose N1 and N4. Proposition 2. If ‖ · | is an asymmetric semi-norm, then ‖x‖ = ‖x|+ ‖ –x| is a semi-norm. Proposition 3. If ‖ · ‖a is an (asymmetric) semi-norm, ‖ · ‖b is a norm (e.g., ‖ · ‖b = ‖ · ‖2), and λ > 0, then ‖x‖a+λb = ‖x‖a + λ‖x‖b is an (asymmetric) norm.

heading: 2.3 WIDE NORMS
text: In addition to Deep Norms, we propose the following alternative method for constructing norms: a Wide Norm is any combination of (asymmetric) (semi-) norms that preserves N1-N4. It 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 so the vector-wise MaxMean combination is valid: maxmean(x1, x2, . . . , xn) = α max(x1, x2, . . . , xn) + (1− α) mean(x1, x2, . . . , xn). Although the family of Wide Norms is broad, for computational reasons to be discussed in 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 of x ∈ Rn, parameterized by W ∈ Rm×n, is defined as ‖x‖W = ‖Wx‖2. It is easily verified that ‖ · ‖W is a proper norm when W is a non-singular (square) matrix, and a semi-norm when W is singular or m < n.
A k-component Mixture of Mahalanobis norm (hereafter Wide Norm, or Wide Norm with k Euclidean components) is defined as the maxmean of k Mahalanobis norms: ‖x‖ = maxmeani (‖Wix‖2) where Wi ∈ Rmi×n with mi ≤ n. (3) 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). N5. ‖ · ‖ is monotonic in the positive orthant if 0 ≤ x ≤ y (element-wise) implies ‖x‖ ≤ ‖y‖. Proposition 4. If ‖ · ‖ is an N5 (semi-) norm on R2n, then ‖x| = ‖relu(x :: –x)‖, where :: denotes concatenation, is an asymmetric (semi-) norm on Rn. Proposition 5. The Mahalanobis norm with W = DU , with D diagonal and U non-negative, is N5.

heading: 2.4 UNIVERSAL APPROXIMATION OF CONVEX FUNCTIONS AND NORMS
text: How expressive are Deep Norms and Wide Norms? Although it was empirically shown that ICNNs have “substantial representation power” (Amos et 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 a series of universal approximation results for ICNNs (with MaxReLU activations), Deep Norms and Wide Norms that use a more practical infinite width construction. The next lemma is central to our results.
Lemma 1 (Semilattice Stone-Weierstrass (from below)). Let C be a set of continuous functions defined on compact subset K of Rn, L be a closed subset of C, and f ∈ C. If (1) for every x ∈ K, there exists gx ∈ L such that gx ≤ f and gx(x) = f(x), and (2) L is closed under max (i.e., a, b ∈ L⇒ max(a, b) ∈ L), then ∃h ∈ L with f = h on K.
Intuitively, Lemma 1 and its proof (Appendix A) say we can approximate continuous f arbitrarily well with a family L of functions that is closed under maximums if we can “wrap” f from below using functions gx ∈ L with gx ≤ f . Our Universal Approximation (UA) results are now straightforward. Theorem 1 (UA for MICNNs). The familyM 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 f ∈ C, x ∈ Rn, let gx ∈ M be a linear function whose hyperplane in the graph of f is tangent to f at x. Then gx satisfies condition (1) of Lemma 1 (because f is convex). The use of pairwise max activations allows one to construct max(h1, h2) ∈ M for any two h1, h2 ∈ 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.
This result applies when MaxReLUs are used, since we can set α, β = 0. Using MaxReLU (rather than max) guarantees that MICNNs can imitate regular ICNNs with at most double the parameters. Theorem 2 (UA for Deep Norms and Wide Norms). The familiesD of Deep Norms (using MaxReLU) andW of Wide Norms (using MaxMean) are dense in the family N of asymmetric semi-norms. Proof (sketch). The proof is almost identical to that of Theorem 1, except that here D andW contain all linear functions whose graph is tangent to any f ∈ N since f is N2. This is easy to see for functions defined on R2. See Appendix A for more details.

heading: 2.5 MODELING NORMS IN 2D
text: Having shown that Deep Norms and Wide Norms universally approximate norms, we now show that they can successfully learn to approximate random norms on R2 when trained using gradient descent. To generate data, we use the below fact, proved in Appendix A. Proposition 6. The set of all asymmetric norms on Rn is in one-to-one correspondence with the set of all bounded and open convex sets (“unit balls”) containing the origin.
We use Proposition 6 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| ∈ {16, 128} training samples of form ((xη, yη), η), where ‖(x, y)‖=1 and η ∼ U(0.85, 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.1 for details.
Figure 3 illustrates the learned 2D norm balls of a 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 3 are the ground truth norm balls for values {0.5, 1, 1.5}, and black contours the norm balls of the learned approximations. With the small dataset, the MLP
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 to being N2), whereas the MLP is unable to generalize to the 0.5 norm ball (indeed, MLP−1(0.5) = ∅). While the symmetric Wide Norm fits well, the results suggest that the asymmetrized Wide Norm is not as effective as the naturally asymmetric Deep Norm. See Appendix C for additional details and visualizations.

heading: 3 MODELING METRICS
text: Having constructed models of asymmetric semi-norms on Rn, we now use them to induce quasimetrics on a domain X . As the geometry of X ’s raw feature space will not, in general, be amenable to a favorable metric (indeed, the raw features need not be in Rn), we assume the Siamese network approach and learn an embedding function, φ : X → Rn. A Deep Norm or Wide Norm ‖ · ‖θ, with parameters θ, is defined on Rn and the metric over X is induced as dφ,θ(x, y) = ‖φ(y) − φ(x)‖θ. We could also define ‖ · ‖θ using an unconstrained neural network (MLP), but this would not be guaranteed to satisfy the norm axioms and induce a quasi-metric.
To illustrate this approach, we revisit Figure 1. To get the results shown, we represent the four nodes as one hot vectors and embed them into R2 using φ(x) = Wx, W ∈ R2×4. We then define the norm on R2 as either a Mahalanobis norm, a Deep Norm, or a Wide Norm. Training the norm and φ together, end-to-end with gradient descent, produces the Figure 1 results.
The choices are summarized in Table 1. 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 a computational advantage when computing pairwise distances for large minibatches, which we explore in Subsection 3.5. Since inducing metrics with Deep Norms or Wide Norms produces a potentially unnecessary homogeneity constraint (due to N2), the next Subsection considers Neural metrics, which offer an approach to relaxing this constraint.

heading: 3.1 NEURAL METRICS
text: Instead of inducing a metric with a norm, we could define a metric directly as a non-negative weighted sum of different metrics. E.g., as we did for Wide Norms, we can define a Wide Metric as the mean of k deep Euclidean metrics. If all components of a Wide Metric are norm-induced, however, it can be induced directly by a single Wide Norm with k components, by setting φ(x) to be the concatenation of the φi(x), and using each Wj 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-induced metrics, it 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-induced metrics (proofs in Appendix A).
Proposition 7 (Metric-preserving concave functions). If d : X × X → R+ is (quasi-) metric, f : R+ → R+, f−1(0) = {0}, and f is concave (i.e., −f is convex), then f ◦ d is (quasi-) metric. Proposition 8 (Max preserves metrics). If d1 and d2 are (quasi-) metric, so too is max(d1, d2).
To use Proposition 7, we note that each unit in the final layer of a Deep Norm defines a metric (assuming gk−1 is non-negative, as it is when using ReLU or MaxReLU activations), as does
each component of a Wide Norm. Thus, by applying metric-preserving functions fi to these metrics, and then combining them using a MaxMean, mean or max, we obtain a valid metric, which we name a Neural Metric. Our k-component fi are parameterized by wi, bi ∈ Rk as follows: fi(x) = minj{wijx+ bij}, where wij ≥ 0, bij ≥ 0, b0 = 0. The advantage of Neural Metrics over plain Deep Norms and Wide Norms is that one can better model certain metrics, such as d(x, y) = min(1, ‖x− y‖). This type of metric might be induced by shortest path lengths in a fully connected graph with some maximum edge weight (for example, a navigation problem with a teleportation device that takes some constant time to operate).
3.2 APPLICATION: METRIC NEARNESS
J (S) MN # (S) ¬M3 J (A) MN # (A) ¬M3
TF 2.01e-2 7.7e3 1.30e-1 3.8e2 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 0
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 O(n3) triangle fixing (“TF”) algorithm for the symmetric case, which iteratively fixes M3 violations and is guaranteed to converge to the global minimum. Table 2 shows that for n = 200, our models (Deep Norm (DN) and Wide Norm (WN) based Neural Metrics) achieve results comparable to that found by 400 iterations of TF in the symmetric case. We note that TF, which approaches the solution through the space of all n× n matrices, produces a non-metric approximation, so that the number of M3 violations (#¬M3) is greater than 0; this said, it is possible to fix these violations by adding a 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 TF algorithm; although our modified TF found a solution , our DN model performed significantly better. See Appendix D for complete experimental details.
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.

heading: 3.3 APPLICATION: MODELING GRAPH DISTANCES
text: In the previous subsection we sought to “fix” a 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 G = (V, E). So long as edge weights are positive and the graph is connected, shortest path lengths are discrete quasi-metrics (n = |V|), and provide an ideal domain for a comparison to the standard Euclidean approach.
Our experiments are structured as a supervised learning task, with inputs x, y ∈ V and targets d(x, y). The targets for a random subset of 150K pairs (of the O(|V |2) 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| ∈ {1K, 2K, 5K, 10K, 20K, 50K}. Nodes were represented using noisy landmark embeddings (see Appendix E). We compare Wide Norms, Deep Norms (ICNN style, with ReLU activations, DNI ), and Deep Norm based Neural Metrics (with MaxReLU and concave activations, DNN ) to the standard Siamese-style Bromley et al. (1994) deep Euclidean metric and MLPs in six graphs, three symmetric and three not, summarized in Table 3a and described in Appendix E. Though MLPs do not induce proper metrics, they are expressive function approximators and serve as a 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/Mahalanobis) network, and oftentimes the MLP reference point as well.

heading: 3.4 APPLICATION: LEARNING GENERAL VALUE FUNCTIONS
text: In this section, we evaluate our models on the task of learning a Universal Value Function Approximator (UVFA) in goal-oriented reinforcement learning (Sutton et al., 2011; Schaul et al., 2015). Figure 4 (left) illustrates the two 11x11 grid world environments, 4-Room and Maze, in which we conduct 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 set of transitions (s, s′, g, r, d) for the state, next state, goal, reward, and done flag, and the UVFA Vθ(s, g) is trained to minimize the temporal difference error via bootstrapped updates with no discounting. We tested several architectures at different training set sizes, which leaves out a portion of transitions such that only a fraction of states or goals were present during training. See Appendix F.1 for details.
Figure 5 summarizes the final generalization performance (on held out (s, g) pairs) for each architecture 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 at 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 4 (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 F.2.
3.5 COMPUTATIONAL CONSIDERATIONS
Several deep metric learning algorithms, such as semihard triplet mining Schroff et al. (2015), involve computing a pairwise distance matrix for large minibatches. 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 ‖x− y‖22 = ‖x‖22 + ‖y‖22 − 2xT y (see Section 4 of Oh Song et al. (2016) for details). This same identity can be 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(n2) approach. To quantify, 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 2 and 3b), these results suggest that only Wide Norms are practical for large mini-batches.

heading: 4 DISCUSSION AND OTHER RELATED WORK
text: Deep Norms, Wide Norms, and Neural Metrics all respect the triangle inequality while universally approximating finite-dimensional asymmetric semi-norms. This allows them to represent metrics that the deep Euclidean Siamese architecture cannot, no matter how deep its embedding function is (see Figure 1). Our models thus provide a 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 5; 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, `p space) by examining the asymptotic “distortion” of embedding n-point metric spaces into Euclidean space. Here the distortion of an embedding φ : X → X ′ of metric space (X , dX ) into metric space (X ′, dX ′) is at most c ≥ 1 if there exists r > 0 such that for all x, y ∈ X , r · dX (x, y) ≤ dX ′(φ(x), φ(y)) ≤ cr · dX (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 is tight (i.e., Θ(log n)) for graph distances in n-point constant-degree expanders. This applies regardless of the dimensionality of the embedding space, and is true for all `p with 1 ≤ p <∞. Future work might investigate the asymptotic distortion of our proposed architectures. On account of the above limitations, others have also proposed non-Euclidean alternatives to learning and representing metrics. To improve expressivity, some have proposed non-parametric 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-Klein metrics, which are not translation-invariant. 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-Klein metrics). As for symmetry, several papers have used asymmetric measures such as KL divergence (Vilnis and McCallum, 2014;
Vendrov et al., 2015; Chen et al., 2016; Ou et al., 2016). To our knowledge, we are the first to propose a parametric measure that is both asymmetric and satisfies the triangle inequality.
Another common approach in deep “metric” learning is to 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, as proper metrics are 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, Scheirer et al. (2014) find that non-metric 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 to be a useful inductive bias (e.g., Hsieh et 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).

heading: 5 CONCLUSION
text: This paper proposed three novel architectures for modeling asymmetric semi-norms and metrics. They can be used instead of the usual Euclidean metric to increase expressiveness while respecting the triangle inequality. We showed that our models outperform Euclidean metrics when used with a 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).

heading: ACKNOWLEDGMENTS
text: We thank Cem Anil, James Lucas, Mitchell Stern, 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.vectorinstitute.ai/ #partners).

heading: A PROOFS
text: In this Appendix, we restate each proposition from the main text and provide a short proof.
Proposition 1. All positive homogeneous convex functions are subadditive; i.e., C1 ∧ N2⇒ N3.
Proof. Putting α = 0.5 in the definition of C1 gives f(0.5x+0.5y) ≤ 0.5f(x)+0.5f(y). Applying N2 on the left and multiplying by 2 gives f(x+ y) ≤ f(x) + f(y) as desired.
Proposition 2. If ‖ · | is an asymmetric semi-norm, then ‖x‖ = ‖x|+ ‖ –x| is a semi-norm.
Proof. ‖x‖ = ‖x| + ‖ –x| = ‖ –x‖, so N4 is satisfied. N2-N3 and non-negativity are similarly trivial.
Proposition 3. If ‖ · ‖a is an (asymmetric) semi-norm, ‖ · ‖b is a norm (e.g., ‖ · ‖b = ‖ · ‖2), and λ > 0, then ‖x‖a+λb = ‖x‖a + λ‖x‖b is an (asymmetric) norm.
Proof. This follows from the positive definiteness of λ‖x‖b and the easily verified fact that nonnegative weighted sums of semi-norms are semi-norms.
Proposition 4. If ‖ · ‖ is an N5 (semi-) norm on R2n, then ‖x| = ‖relu(x :: –x)‖, where :: denotes concatenation, is an asymmetric (semi-) norm on Rn.
Proof. N1 and N2 are easily verified. To see that ‖ · | is not necessarily symmetric, choose ‖ · ‖ to be a Mahalanobis norm parameterized by a diagonal W with Wii = i (but NB that if ‖ · ‖ is invariant to element-wise permutations, as are the Lp norms, ‖ · | will be symmetric). For N3, we have:
‖x|+ ‖y| = ‖relu(x :: –x)‖+ ‖relu(y :: – y)‖ ≥ ‖relu(x :: –x) + relu(y :: – y)‖ ≥ ‖relu(x+ y :: – (x+ y))‖ = ‖x+ y|.
The first inequality holds because ‖ · ‖ is N3. The second holds because ‖ · ‖ is N5, and we have either element-wise equality (when sign(xi) and sign(yi) agree) or domination (when they don’t).
Proposition 5. The Mahalanobis norm with W = DU , with D diagonal and U non-negative, is N5.
Proof. Let ‖ · ‖ be ‖ · ‖2, and 0 ≤ x ≤ y = x+ . We have:
‖Wx‖‖Wy‖ ≥ |(Wx)T (Wy)| = xWTW (x+ )
= xWTWx+ xUTDTDU
≥ ‖Wx‖2.
The first inequality is Cauchy-Schwarz. The second holds as all elements of x, UTDTDU , and are non-negative.
Lemma 1 (Semilattice Stone-Weierstrass (from below)). Let C be a set of continuous functions defined on compact subset K of Rn, L be a closed subset of C, and f ∈ C. If (1) for every x ∈ K, there exists gx ∈ L such that gx ≤ f and gx(x) = f(x), and (2) L is closed under max (i.e., a, b ∈ L⇒ max(a, b) ∈ L), then ∃h ∈ L with f = h on K.
Proof. Fix > 0 and consider the sets Ux = {y | y ∈ K, f(y) − < gx(y)}, for all x ∈ K. The Ux form an open cover of K, so there is a finite subcover {Ux1 , Ux2 , . . . , Uxn}. Let g = max(gx1 , gx2 , . . . , gxn) ∈ L. We have f − ≤ g ≤ f , and the result follows since L is closed.
Theorem 1 (UA for MICNNs). The familyM 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 f ∈ C, x ∈ Rn, let gx ∈ M be a linear function whose hyperplane in the graph of f is tangent to f at x. Then gx satisfies condition (1) of Lemma 1 (because f is convex). The use of pairwise max activations allows one to construct max(h1, h2) ∈ M for any two h1, h2 ∈ 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.
Theorem 2 (UA for Deep Norms and Wide Norms). The familiesD of Deep Norms (using MaxReLU) andW 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 1. The only subtlety is that D andW do not contain all linear functions in Rn; they do, however, contain all linear functions whose hyperplane is tangent to any f ∈ N , since f is N2. This is easy to see for functions defined on R2. To generalize the intuition to Rn, consider the ray Rx = {(αx :: α‖x‖) |α ≥ 0} ⊂ Rn+1 defined for each x ∈ Rn. By N2, this ray is a subset of the graph g ⊂ Rn+1 of f . Furthermore, any hyperplane tangent to one point on this ray is 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 x is tangent to a point (x) on the ray Rx, and so contains the origin. Since D andW 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 Lemma 1 (because f is convex). For Deep Norms, the use of pairwise max activations allows one to construct a global max operation, as in the proof of Theorem 1, satisfying condition (2) of Lemma 1. Wide Norms using MaxMean have direct access to a global max, and so satisfy condition (2) of Lemma 1. It follows that f is in the closures of D andW .
Proposition 6. The set of all asymmetric norms on Rn is in one-to-one correspondence with the set of all bounded and open convex sets (“unit balls”) containing the origin.
Proof. Given asymmetric norm ‖ · ‖ on Rn, its unit ball B1 := {x | ‖x‖ < 1} is convex since, ∀x, y ∈ B1, λ ∈ [0, 1], we have ‖(1 − λ)x + λy‖ ≤ (1 − λ)‖x‖ + λ‖y‖ ≤ 1 (using N3 & N2). Conversely, given open and bounded convex set B1 containing the origin, let ‖x‖ = inf{α > 0 | xα ∈ B1}. N1 and N2 are straightforward and N3 follows by noting that for x, y ∈ Rn, α, β > 0, such that xα , y β ∈ B1, we have α α+β x α + β α+β y β = x+y α+β ∈ B1, so that inf{γ > 0 | x+y γ ∈ B1} ≤ inf{α > 0 | xα ∈ B1}+ inf{β > 0 | y β ∈ B1}.
Proposition 7 (Metric-preserving concave functions). If d : X × X → R+ is (quasi-) metric, f : R+ → R+, f−1(0) = {0}, and f is concave (i.e., −f is convex), then f ◦ d is (quasi-) metric.
Proof. This proposition is proven for metrics by Doboš (1998) (Chapter 1, Theorem 3). The extension to quasi-metrics is immediate, as the proof does not require symmetry.
Proposition 8 (Max preserves metrics). If d1 and d2 are (quasi-) metric, so too is max(d1, d2).
Proof. M1 and M2 are trivial. For M3, let d = max(d1, d2). Given some x, y, z, we have both d1(x, y)+d1(y, z) ≥ d1(x, z) and d2(x, y)+d2(y, z) ≥ d2(x, z), so that d(x, y)+d(y, z) ≥ d1(x, z) and d(x, y)+d(y, z) ≥ d2(x, z) . Therefore, d(x, y)+d(y, z) ≥ max(d1(x, z), d2(x, z)) = d(x, z). 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 Chen 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 Wi for i < k to be non-negative by clipping the parameter matrix after each gradient update. For Wk, we use either a simple mean or MaxMean (see Subsection 2.3). We set Uk = 0. We use either ReLU or MaxReLU for our activations gi, as noted.
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 k = 3 layers of sizes (400, 400, 1) is a “2x400” Deep Norm.
Our Wide Norm implementation avoids parameterizing the αi in Equation 3 by absorbing them into the weight matrices, so that ‖x‖ = 1k ∑ i ‖Uix‖2, where Ui = αikWi. Our asymmetric Wide Norm constrains matrix U of Proposition 5 by clipping negative values and does not use matrix D (i.e., we 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 pseudometric problems (where d(x, y) = 0 is possible for distinct x, y ∈ X ). Neural Metrics involve only a very small modification to Deep Norms and Wide Norms: before applying the mean or MaxMean global activation to obtain the final output, we apply an element-wise concave activation function, as described in Subsection 3.1.
C 2D NORMS ADDITIONAL DETAILS
Dataset generation To generate data, we use Proposition 6 by generating a 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 a random norm, we sample a set of N = 500 unit vectors in R2 (according to L2) in random directions, then scale the vectors until they intersect the convex hull: {x}N . We use these vectors for testing data, defined as Dtest = {(x(1), 1), ..., (x(N), 1)}. For training data, we sample a size |D| = {16, 128} subset of these vectors and multiply them by random perturbations (i) ∼ U(0.85, 1.15) to get {x̂ |x̂(i) = x(i) (i)}k. The training data is then defined as Dtrain = {(x̂(1), (1)), ..., (x̂(k), (k))}.
Models We compare 4 model types on 4 types of norms. The models are (1) Mahalanobis, (2) Deep Norms of depth ∈ {2, 3, 4, 5} and layer size ∈ {10, 50, 250}, (3) Wide Norms of width ∈ {2, 10, 50} and number of components ∈ {2, 10, 50}, and (4) unconstrained, fully connected neural networks with ReLU activations of depth ∈ {2, 3, 4, 5} and layer size ∈ {10, 50, 250} (MLPs). Although MLPs do not generally satisfy N1-N4, we are interested in how they generalize without the architectural inductive bias.
Norms The norms we experiment on are random (1) symmetric and (2) asymmetric norms, constructed as above, and (3) square (L∞), and (4) diamond (L1) norms.
Training The models, parameterized by θ, are trained to minimize the mean squared error (MSE) between the predicted (scalar) norm value ‖x̂(i)‖ and the label norm value (i): L(θ) = 1 M ∑M i (‖x̂(i)‖θ − (i))2, where M = 16 is the batch size. We use Adam Optimizer Kingma and Ba (2014), with learning rate 1e-3, and train for a maximum of 5000 epochs.
Results Tables 5-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 3 illustrates the learned norm balls for random symmetric and asymmetric norms, when trained with small (k = 16) and large (k = 128) data sizes. Appendix C includes 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 R2, we generated c ∈ [3, 10] clusters, each with ni ∈ [5, 50] random points. The points for each cluster were sampled from a truncated normal distribution with µi ∼ U(−0.5, 0.5) and σ(i) ∼ U(0.2, 0.6), truncated to 2 standard deviations. For symmetric sets, we considered only
those points with positive x-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) ConvexHull implementation.
C.2 ADDITIONAL VISUALIZATIONS
Figure 8 and Figure 7 further visualizes the training data and the Mahalanobis architecture in addition to the MLP, Deep Norm, and Wide Norm architectures, for the random symmetric, asymmetric, square (L∞) and the diamond (L1) unit ball shape.

heading: D METRIC NEARNESS ADDITIONAL DETAILS
text: Dataset creation For the symmetric metric nearness dataset, we generated the data as was found in Sra et al. (2005): a random matrix in R200×200 was generated with values drawn from the uniform distribution ranging between 0 and 5. This matrix was added to its transpose to make it symmetric. Random uniform noise was added to each entry between 0 and 1, then the diagonal was removed. For the asymmetric case, a more complex dataset creation strategy was employed due to the fact that a random asymmetric matrix generated as above was too difficult a 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 A∗ algorithm. Then, again, random uniform noise between 0 and 4 was added to 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 a metric.
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 a 512-dimensional embedding function, 5-unit concave activation functions, and MaxMean global pooling. The deep Euclidean architecture used a 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 convergence. For the symmetric case we reimplemented Sra et al. (2005) in Python using their C++ code as a 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 in total split up in to 500 epoch chunks were the learning rate decreased from 1e-3 to 3e-4 to 1e-4 at the end, using a batch size of 1000. We used the Adam optimizer Kingma and Ba (2014) with default hyperparameters. Results were averaged over 10 seeds.

heading: E GRAPH EXPERIMENTS ADDITIONAL DETAILS
text: Symmetric graph descriptions The first symmetric graph, to, consists of a symmetrized road network extracted from openStreetMap (OSM, www.openstreetmap.org). The second, 3d, represents navigation in a 50x50x50 cubic 3d gridworld, where the agent can move one step at a time in 6 directions, and movement wraps around the sides of the cube. The third, taxi, represents a 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 no 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).
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 a 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 a 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 x, y ∈ V and targets d(x, y). The targets for a random subset of 150K pairs (of the O(|V |2) 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| ∈ {1K, 2K, 5K, 10K, 20K, 50K}. 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’s 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 0 and standard deviation 1, and noise sampled from N (0, 0.2) was added. To add additional noise through distractor features, 96 normally distributed features were concatenated with the noisy landmark features to obtain node embeddings with 128 dimensions for symmetric graphs and 160 dimensions for asymmetric graphs. We also tested node2vec embeddings Grover and Leskovec (2016), 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 a 128-dimensional Mahalanobis metric (equivalent to a deep Euclidean metric with an additional layer), a Wide Norm based Neural Metric (32 components of 32 units, with 5-unit concave activations, and MaxMean global pooling), a plain Deep Norm (3 layers of 128 units, ICNN style with ReLU activations, no concave activations, and average pooling, DNI ), and a Deep Norm based Neural Metric (3 layers of 128 units, with MaxReLU and 5-unit concave activations, and MaxMean pooling, DNN ), and an MLP (3 layers of 128 units). We train each algorithm with 4 different embedding functions φ, each a fully connected, feed-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 1e-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 11 below.

heading: F GENERAL VALUE FUNCTIONS ADDITIONAL DETAILS
text: F.1 EXPERIMENTAL DETAILS
4-Room and Maze environment description The fully observable grid environment has a state and goal representation of a binary tensor with dimensions 11 × 11 × 3. Each cell in the 2D grid is represented by a 1-hot vector with 3 dimensions, indicating whether the cell is (1) empty, (2) wall, (3) agent. The agent can move up to 4 cardinal directions (North, South, East, West). If a 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 a neighbour function N(s) 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, a) over all the actions.
Transition reward and episode termination For symmetric environments, every transition has a reward of -1, i.e., R(s, s′) = −1. Note that reward is not a function of the goal, but the termination is. For asymmetric environments, we add a noise µ ∼ U(0,−5) to the base −1 reward for a transition if the direction of movement is west (left) or south (down). The done flag is set to 1 when the neighbouring state equals to the goal, i.e. D(s, s′, g) = [s′ = g].
Choosing Training-Test Split Dataset Given the full training data set of (s, g) pairs, we use 2 types of splitting into train and test datasets: (1) goal, and (2) state. We denote the training fraction η =∈ [0, 1] as the fraction of the total data points used for the training set. For goal splitting, we pick a subset of goals {g∗} ⊆ g with |{g∗}| ≈ (1 − η)|{g}|, and remove all (s, g) pairs where g ∈ g∗, from the training set. These goals were chosen to be the percentage of empty cells from the bottom of the grid, when numbering the empty cells from left to right, and top-down (i.e. reading order of words in a page). This corresponds to approximately a fraction of the bottom rows of goals. In 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 a 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.
Architecture The architectures used for the experiments consist of a shared feature extractor φ for the state s and goal g, followed by a function fθ on the difference of the features:
V (s, g;φ, θ) = fθ(φ(g)− φ(s)) (4)
The feature extractor φ is composed of 2 convolutional layers with 3 × 3 kernel size, and 32 and 62 filters with ReLU activations and a stride of 1. We then flatten the feature maps and follow by 2 fully connected layers of hidden size 128 and 64, with ReLU activation on the first layer only. The variants of fθ are summarized in table 8. Euclidean simply computes the L2 norm between the feature embeddings: ‖φ(g)− φ(s)‖2:
Training The objective function for training the models is the Temporal Difference (TD) Error L(φ, θ):
L(φ, θ) = E(s,g)∼D [( V (s, g;φ, θ)− y )2] , (5)
y =
{ r(s, s′, g) + maxs′∈N(s) V (s
′, g; φ̄, θ̄), if s′ 6= g r(s, s′, g), otherwise
(6)
Where N(s) refers to the set of next states of s after applying different actions at that state. Note that we did not apply a discount factor on the value of the next state (i.e. the discount factor γ = 1). We make use of target networks φ̄, θ̄ 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 (φ, θ):
θ̄(n+1) = αθ̄(n) + (1− α)θ(n), (7)
where, α = 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.
Evaluation Metrics We evaluate the learned value functions on several metrics: MSE, Policy Success, and SPL 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 s, and follow a greedy policy to visit the neighbour s′ = arg max′s r(s, s
′) + V (s′) for up to T = 121 timesteps (11 × 11). If the agent reaches the desired goal within the episode i then the binary success indicator Si = 1 and the episode terminates, and 0 otherwise. Let li be the ground truth V (s, g) optimal episode cumulative reward (i.e. path cost), and pi the cumulative reward in the episode by the agent’s trajectory. We then define the Policy Success rate and SPL as:
Success = 1
N N∑ i=1 Si, SPL = 1 N N∑ i=1 Si li max(pi, li) (8)
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 16), and (3) SPL metric for individual (s0, s) and (s, s0) pairs (Figure 17). These results are for agents trained with training fraction η = 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 13a), (2) Train (Figure 14a) 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.

Review summaries:
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).

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.