Title: AN INDUCTIVE BIAS FOR DISTANCES: NEURAL NETS THAT RESPECT THE TRIANGLE INEQUALITY

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 guaranteesand empirically-as an inductive bias. Deep metric learning architectures that respect the triangle inequality rely, almost exclusively, on Euclidean distance in the latent space. Though effective, this fails to model two broad classes of subadditive distances, common in graphs and reinforcement learning: asymmetric metrics, and metrics that cannot be embedded into Euclidean space. To address these problems, we introduce novel architectures that are guaranteed to satisfy the triangle inequality. We prove our architectures universally approximate norm-induced metrics on R n , and present a similar result for modified Input Convex Neural Networks. We show that our architectures outperform existing metric approaches when modeling graph distances and have a better inductive bias than non-metric approaches when training data is limited in the multi-goal reinforcement learning setting.

1. 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)-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 d X : X × X → R + on domain X by learning embedding φ : X → R n and computing d X (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 , d X ), including large classes of symmetric graphs (e.g., constant-degree expanders and k-regular graphs), there is no embedding φ : X → R n that can model d X 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 The nodes in the graph (left) cannot be embedded into any R n 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 R 2 (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.

2. MODELING NORMS:

2.1 PRELIMINARIES 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.

2.2. DEEP NORMS:

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. The proof is straightforward (put α = 1 2 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:

EQUATION

for i = 1...k, where x is the input, h 0 = 0, W + 1 = 0, the activation functions g i preserve C1 and N2 (element-wise), g k is non-negative, W + i is a non-negative matrix, and U i is an unconstrained matrix. As compared to the original ICNN architecture, we have omitted the bias terms from Equation 1, have constrained the g i 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 g k to be non-negative. It is easy to verify that the set of valid element-wise g i 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.

2.3. WIDE NORMS:

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(x 1 , x 2 , . . . , x n ) = α max(x 1 , x 2 , . . . , x n ) + (1 -α) mean(x 1 , x 2 , . . . , x n ).

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 ∈ R n , parameterized by W ∈ R m×n , is defined as x W = W x 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 = maxmean i ( W i x 2 )

where W i ∈ R mi×n with m i ≤ 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 R 2n , then x| = relu(x :: -x)

, where :: denotes concatenation, is an asymmetric (semi-) norm on R n . Proposition 5. The Mahalanobis norm 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 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 R n , L be a closed subset of C, and f ∈ C. If (1) for every x ∈ K, there exists g x ∈ L such that g x ≤ f and g x (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 g x ∈ L with g x ≤ f . Our Universal Approximation (UA) results are now straightforward. Theorem 1 (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 f ∈ C, x ∈ R n , let g x ∈ M be a linear function whose hyperplane in the graph of f is tangent to f at x. Then g x satisfies condition (1) of Lemma 1 (because f is convex). The use of pairwise max activations allows one to construct max(h 1 , h 2 ) ∈ M for any two h 1 , h 2 ∈ M by using log 2 (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 families D 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 is almost identical to that of Theorem 1, except that here D and W 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 R 2 . See Appendix A for more details.

2.5. MODELING NORMS IN 2D:

Having shown that Deep Norms and Wide Norms universally approximate norms, we now show that they can successfully learn to approximate random norms on R 2 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 R n 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. 

3. MODELING METRICS:

Having constructed models of asymmetric semi-norms on R n , 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 R n ), we assume the Siamese network approach and learn an embedding function, φ : X → R n . A Deep Norm or Wide Norm • θ , with parameters θ, is defined on R n 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 R 2 using φ(x) = W x, W ∈ R 2×4 . We then define the norm on R 2 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.

3.1. NEURAL METRICS:

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 W j 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 d 1 and d 2 are (quasi-) metric, so too is max(d 1 , d 2 ).

To use Proposition 7, we note that each unit in the final layer of a Deep Norm defines a metric (assuming g k-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 f i 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 f i are parameterized by w i , b i ∈ R k as follows:

f i (x) = min j {w ij x + b ij }, where w ij ≥ 0, b ij ≥ 0, b 0 = 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) M N # (S) ¬M3 J (A) M N # (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

Table 2: Metric nearness for sym. (S) and asym. (A) matrices in R 200×200 (10 seeds).

We now apply our models to the metric nearness problem (Sra et al., 2005; Brickell et al., 2008) . In this problem, we are given a matrix of pairwise nonmetric distances between (finite) n objects, and it is desired to minimally repair the data to satisfy metric properties (the triangle inequality, M3, in particular). Formally, given data matrix D ∈ R n×n , we seek metric solution X ∈ R n×n that minimizes the "distortion" J M N = X -D 2 / D 2 (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 O(n 3 ) 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 J M N . 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.

3.3. APPLICATION: MODELING GRAPH DISTANCES:

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). 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. 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(n 2 ) 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.

3.5. COMPUTATIONAL CONSIDERATIONS:



4. DISCUSSION AND OTHER RELATED WORK:

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 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.

φ : X → X of metric space (X , d X ) into metric space (X , d X ) is at most c ≥ 1 if there exists r > 0 such that for all x, y ∈ X , r • d X (x, y) ≤ d X (φ(x), φ(y)) ≤ cr • d X (x, y). The pioneering work of

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) .

5. CONCLUSION:

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) .

A PROOFS:

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. 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 R 2n , then x| = relu(x :: -x) , where :: denotes concatenation, is an asymmetric (semi-) norm on R n .

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 W ii = i (but NB that if • is invariant to element-wise permutations, as are the L p 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(x i ) and sign(y i ) 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:

W x W y ≥ |(W x) T (W y)| = xW T W (x + ) = xW T W x + xU T D T DU ≥ W x 2 .

The first inequality is Cauchy-Schwarz. The second holds as all elements of x, U T D T DU , 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 R n , L be a closed subset of C, and f ∈ C. If (1) for every x ∈ K, there exists g x ∈ L such that g x ≤ f and g x (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 U x = {y | y ∈ K, f (y) -< g x (y)}, for all x ∈ K.

The U x form an open cover of K, so there is a finite subcover {U x1 , U x2 , . . . , U xn }. Let g = max(g x1 , g x2 , . . . , g xn ) ∈ L. We have f -≤ g ≤ f , and the result follows since L is closed.

Theorem 1 (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 f ∈ C, x ∈ R n , let g x ∈ M be a linear function whose hyperplane in the graph of f is tangent to f at x. Then g x satisfies condition (1) of Lemma 1 (because f is convex). The use of pairwise max activations allows one to construct max(h 1 , h 2 ) ∈ M for any two h 1 , h 2 ∈ M by using log 2 (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 families D of Deep Norms (using MaxReLU) 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 1. The only subtlety is that D and W do not contain all linear functions in R n ; 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 R 2 . To generalize the intuition to R n , consider the ray R x = {(αx

:: α x ) | α ≥ 0} ⊂ R n+1 defined for each x ∈ R n .

By N2, this ray is a subset of the graph g ⊂ R n+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 R x , and so contains the origin. Since D 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 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 and W.

Proposition 6. The set of all asymmetric norms on R n 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 R n , its unit ball

B 1 := {x | x < 1} is convex since, ∀x, y ∈ B 1 , λ ∈ [0, 1], we have (1 -λ)x + λy ≤ (1 -λ) x + λ y ≤ 1 (using N3 & N2).

Conversely, given open and bounded convex set B 1 containing the origin, let x = inf{α > 0 | x α ∈ B 1 }. N1 and N2 are straightforward and N3 follows by noting that for x, y ∈ R n , α, β > 0, such that x α , y β ∈ B 1 , we have

α α+β x α + β α+β y β = x+y α+β ∈ B 1 , so that inf{γ > 0 | x+y γ ∈ B 1 } ≤ inf{α > 0 | x α ∈ B 1 } + inf{β > 0 | y β ∈ B 1 }. 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 d 1 and d 2 are (quasi-) metric, so too is max(d 1 , d 2 ).

Proof. M1 and M2 are trivial. For M3, let d = max(d 1 , d 2 ). Given some x, y, z, we have both

d 1 (x, y)+d 1 (y, z) ≥ d 1 (x, z) and d 2 (x, y)+d 2 (y, z) ≥ d 2 (x, z), so that d(x, y)+d(y, z) ≥ d 1 (x, z) and d(x, y) + d(y, z) ≥ d 2 (x, z) . Therefore, d(x, y) + d(y, z) ≥ max(d 1 (x, z), d 2 (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 W i for i < k to be non-negative by clipping the parameter matrix after each gradient update. For W k , we use either a simple mean or MaxMean (see Subsection 2.3). We set U k = 0. We use either ReLU or MaxReLU for our activations g i , 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 = 1 k i U i x 2 , where U i = α i kW i . 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 R 2 (according to L 2 ) in random directions, then scale the vectors until they intersect the convex hull: {x} N . We use these vectors for testing data, defined as D test = {(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 D train = {(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 (L 1 ) 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 6 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 R 2 , we generated c ∈ [3, 10] clusters, each with n i ∈ [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

Maha DN WN MLP sym 16 3.4×10 -3 1.5×10 -5 6.7×10 -5 1.5×10 -3 128 3.2×10 -3 7.8×10 -7 1.0×10 -6 1.2×10 -5 asym 16 1.7×10 -1 4.1×10 -4 4.9×10 -3 1.6×10 -3 128 1.7×10 -1 2.5×10 -5 4.5×10 -3 3.0×10 -5 square 16 1.7×10 -2 3.0×10 -5 2.4×10 -9 7.7×10 -3 128 1.1×10 -2 2.1×10 -6 9.3×10 -9 7.8×10 -6 diamond 16 1.2×10 -2 6.5×10 -4 4.6×10 -8 2.2×10 -3 128 1.1×10 -2 4.5×10 -7 2.3×10 -10 7.8×10 -6

Table 5 : MSE on 2d norm test set (target norm 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.4×10 -2 6.0×10 -5 2.7×10 -4 3.8×10 -2 128 1.3×10 -2 3.1×10 -6 4.0×10 -6 2.3×10 -2 asym 16 6.7×10 -1 1.6×10 -2 2.0×10 -2 2.0×10 -1 128 6.7×10 -1 2.0×10 -4 1.8×10 -2 2.8×10 -2 square 16 6.8×10 -2 1.2×10 -4 9.6×10 -9 2.7×10 -1 128 4.4×10 -2 8.3×10 -6 3.7×10 -8 6.1×10 -3 diamond 16 4.6×10 -2 2.6×10 -3 1.9×10 -7 4.1×10 -1 128 4.4×10 -2 1.8×10 -6 9.3×10 -10 7.4×10 -2

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 -4 3.7×10 -6 1.7×10 -5 4.5×10 -2 128 8.1×10 -4 2.0×10 -7 2.5×10 -7 1.2×10 -2 asym 16 4.2×10 -2 1.0×10 -4 1.2×10 -3 7.9×10 -2 128 4.2×10 -2 6.2×10 -6 1.1×10 -3 7.6×10 -2 square 16 4.3×10 -3 7.5×10 -6 6.0×10 -10 7.5×10 -2 128 2.7×10 -3 5.2×10 -7 2.3×10 -9 1.0×10 -2 diamond 16 2.9×10 -3 1.6×10 -4 1.2×10 -8 1.0×10 -1 128 2.8×10 -3 1.1×10 -7 5.8×10 -11 2.5×10 -2

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.

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. 

D METRIC NEARNESS ADDITIONAL DETAILS:

Dataset creation For the symmetric metric nearness dataset, we generated the data as was found in Sra et al. (2005) : a random matrix in R 200×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. 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. 

Architectures used:



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.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 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]. 

:

Code available at https://github.com/spitis/deepnorms

Figures and Tables:

Fig.1: The nodes in the graph (left) cannot be embedded into any R n 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 R 2 (middle). The visualization (right) shows learned norm balls in red and embeddings in blue.

Fig. 2: Deep Norm architecture.

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

Fig. 4: GVF environments. Left: 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 s 0 denotes agent at top left cell. Upper triangular regions indicate the value of V (s 0 , s) while lower indicate V (s, s 0 ). Center: Squared Error (SE) heatmap between the learned and ground truth value for WideNorm and MLP 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.5: GVF results. Generalization as measured by SPL metric (higher is better) on held out (s, g) pairs as function of fraction of goals seen during training. Results averaged over 3 seeds and error bar indicates standard deviation. For fraction = 1 we evaluate on entire data.

If • | is an asymmetric semi-norm, then x = x| + -x| is a semi-norm. Proof. x = x| + -x| = -x , so N4 is satisfied. N2-N3and 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.

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 (L 1 ) unit ball shape.

Fig. 8: Visualization of the 2d unit circles learned by several architectures (see Section 2.5) for a symmetric and asymmetric shape convex hull, corresponding to L ∞ and L 1 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}.

Fig. 9: Learning curves on symmetric metric nearness.

Fig. 10: Symmetric graph learning curves.

Fig. 11: Asymmetric graph learning curves.

Fig.13: Additional performance on the train/test SPL metric vs training fraction for the four environment variants (higher is better).

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).

Fig. 15: Learned Value Function for the four environments with Train Fraction = 0.75.

Norm

Table content: <table><tr><td>(metric) properties of different architectures. As compared to Euclidean architectures,</td></tr><tr><td>ours are universal asymmetric semi-norm approximators (UA) and can use propositions to optionally</td></tr><tr><td>satisfy (6) N1 and N4. Neural metrics relax the unnecessary homogeneity constraint on metrics.</td></tr><tr><td>overfits to the training data and generalizes poorly, while Deep Norm and Wide Norm generalize</td></tr><tr><td>almost perfectly. With the large dataset, we observe that Deep Norms and Wide Norms generalize to</td></tr><tr><td>larger and smaller norm balls (due to being N2), whereas the MLP is unable to generalize to the 0.5</td></tr><tr><td>norm ball (indeed, MLP -1 (0.5) = ∅). While the symmetric Wide Norm fits well, the results suggest</td></tr><tr><td>that the asymmetrized Wide Norm is not as effective as the naturally asymmetric Deep Norm. See</td></tr><tr><td>Appendix C for additional details and visualizations.</td></tr></table>

The targets for a random subset of 150K pairs (of the O(|V | 2 ) total pairs) were computed beforehand

Table content: <table><tr><td/><td>|V|</td><td>|E|</td><td colspan="2">max(d) σ d</td><td>Sym?</td><td/><td>Eucl.</td><td>WN</td><td>DNI</td><td>DNN</td><td>MLP</td></tr><tr><td>to</td><td>278K</td><td>611K</td><td>145.7</td><td>24.5</td><td>↔</td><td>to</td><td>12.5</td><td>6.6</td><td>6.7</td><td>6.7</td><td>12.3</td></tr><tr><td>3d</td><td>125K</td><td>375K</td><td>86.7</td><td>13.2</td><td>↔</td><td>3d</td><td>31.2</td><td>17.3</td><td>15.4</td><td>12.9</td><td>20.6</td></tr><tr><td colspan="2">taxi 391K</td><td>752K</td><td>111.2</td><td>13.4</td><td>↔</td><td>taxi</td><td>14.4</td><td>10.6</td><td>11.8</td><td>11.4</td><td>5.8</td></tr><tr><td colspan="4">push 390K 1498K 113.1</td><td>14.3</td><td>→</td><td>push</td><td>22.2</td><td>14.0</td><td>14.7</td><td>13.5</td><td>11.3</td></tr><tr><td>3dr</td><td>123K</td><td>368K</td><td>86.5</td><td>13.1</td><td>→</td><td>3dr</td><td>22.0</td><td>17.5</td><td>21.8</td><td>18.3</td><td>25.5</td></tr><tr><td>3dd</td><td>125K</td><td>375K</td><td>97.8</td><td>13.4</td><td>→</td><td>3dd</td><td>211.8</td><td>177.1</td><td>199.5</td><td>157.7</td><td>252.7</td></tr><tr><td/><td/><td colspan="2">(a) Graph statistics</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>



Table content: <table/>

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.

Table content: <table/>

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, DN I ), and a Deep Norm based Neural Metric (3 layers of 128 units, with MaxReLU and 5-unit concave activations, and MaxMean pooling, DN N ), 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.

Table content: <table><tr><td>Training Training was done end-to-end with Adam Optimizer Kingma and Ba (2014), using an</td></tr><tr><td>initial learning rate of 1e-3 and a batch size of 256. Networks were each trained for 1000 total epochs,</td></tr><tr><td>and the learning rate was divided by 5 every 250 epochs.</td></tr><tr><td>Results The complete results/learning curves are displayed in Figures 10 and 11 below.</td></tr><tr><td>F GENERAL VALUE FUNCTIONS ADDITIONAL DETAILS</td></tr><tr><td>F.1 EXPERIMENTAL DETAILS</td></tr><tr><td>4-Room and Maze environment description The fully observable grid environment has a state</td></tr><tr><td>and goal representation of a binary tensor with dimensions 11 × 11 × 3. Each cell in the 2D grid</td></tr><tr><td>is represented by a 1-hot vector with 3 dimensions, indicating whether the cell is (1) empty, (2)</td></tr><tr><td>wall, (3) agent. The agent can move up to 4 cardinal directions (North, South, East, West). If a</td></tr><tr><td>wall is present in the direction then the agent cannot take that move. The 4-Room environment</td></tr><tr><td>and Maze environment has a total of 4556 and 2450 training (s, g) pairs, respectively. For each</td></tr><tr><td>environment, the agent has access to a neighbour function N (s) which returns a list of possible next</td></tr><tr><td>states, corresponding to the empty cells adjacent to the current agent location. This is equivalent to</td></tr><tr><td>having environment transition model p(s |s, a) over all the actions.</td></tr></table>

Peer review (iclr2020):
This paper proposes a modeling approach for norm and metric learning that ensures triangle inequalities are satisfied by the very design of the architecture. The main idea is that convexity together with homogeneity imply subadditivity, so starting from an input-convex architecture and using activations that preserve homogeneity implies the resulting model is sub-additive at every point. This architecture is used to model a norm, and in conjunction with an embedding - a metric. The authors also propose a mixture-based approach that combines a given set of metrics into a new one using a max-mean approach. Universal approximation results are presented for both architectures. The results are illustrated on a few mostly synthetic examples including metric nearness for random matrices, value functions for maze MDPs and distances between nodes on a graph (some problems here are sourced from open street map). I think this is one of those papers where there is nothing much to complain about. I found the paper to be very-well written. The basic modeling approach of propagating homogeneity through an input-convex net is elegant, and conceptually appealing. My only suggestion to the authors is that it looks as if a lot of importance is placed on modeling asymmetry, however, that problem seems relatively easily solvable with existing approaches. One could just have two separate embedding functions for the two positional arguments. I don*t know if there are obvious reasons why this wouldn*t work, but it looks like a very sensible idea that could solve asymmetry. I think that the other issue, that of nonembeddability is much more important, yet it was not emphasized particularly strongly except for one example. I think expanding on this would strengthen the motivation significantly. There is a rich literature on (non)embeddability in l2, which contains some deeply non-intuitive results (e.g. large graph classes like expanders being non-embeddable). I think that a quick survey on that citing the most important results would make the seriousness of this issue apparent to the reader.