On the Learning and Learnability of Quasimetrics
Authors: Tongzhou Wang
Phillip Isola
Venue: ICLR 2022 Poster (2022)
Keywords: embedding learning
quasimetric learning
deep learning

Abstract: Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical). Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, little research has been done on the learning of quasimetrics. Our theoretical analysis reveals that a common class of learning algorithms, including unconstrained multilayer perceptrons (MLPs), provably fails to learn a quasimetric consistent with training data. In contrast, our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate its effectiveness over many common baselines.

Published as a conference paper at ICLR 2022
ON THE LEARNING AND LEARNABILITY OF QUASIMETRICS
Tongzhou Wang MIT CSAIL
Phillip Isola MIT CSAIL
ABSTRACT
Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical). Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, little research has been done on the learning of quasimet- rics. Our theoretical analysis reveals that common class of learning algorithms, including unconstrained multilayer perceptrons (MLPs), provably fails to learn quasimetric consistent with training data. In contrast, our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate its effectiveness over many common baselines.
Project Page:
ssnl. gi thub.
Code:
gi t
INTRODUCTION
Learned symmetrical metrics have been proven useful for innumerable tasks including dimensionality reduction (Tenenbaum et al., 2000), clustering (Xing et al., 2002), classification (Weinberger et al., 2006; Hoffer & Ailon, 2015), and information retrieval (Wang et al., 2014). However, the real world is largely asymmetrical, and symmetricaal metrics can only capture small fraction of it.
Generalizing metrics, quasimetrics (Defn. 2.1) allow for asymmetrical distances and can be found in wide range of domains (see Fig. 1). Ubiquitous physical forces, such gravity and wind, well as human-defined rules, such as one-way roads, make the traveling time between places a quasimetric. Furthermore, many of social artifacts are directed graphs- genealogy charts, follow-relation on Twitter (Leskovec & Krevl, 2014), citation graphs (Price, 201 1), hyperlinks over the Internet, etc. Shortest paths on these graphs naturally induce quasimetric spaces. In fact, we can generalize to Markov Decision Processes (MDPs) and observe that optimal goal-reaching plan costs (i.c., universal Balue/Q-functions (Schaul et al., 2015; Sutton et al., 2011)) always form quasimetric (Bertsekas & Tsitsiklis, 1991; Tian et al., 2020). Moving onto more abstract structures, quasimetrics can also be found as expected hitting times in Markov chains, and as conditional Shannon entropy H in information theory. (See the appendix for proofs and discussions of these quasimetrics.)
In this work, we study the task of quasimetric learning. Given a sampled training set of pairs and their quasimetric distances, we ask: how well can we learn a quasimetric that fits the training data? We define quasimetric learning in analogy to metric learning: whereas metric learning is the problem of learning metric function, quasimetric learning is the problem of learning a quasimetric function. This may involve searching over a hypothesis space constrained to only include quasimetric functions (which is what our method does) or it could involve searching for approximately quasimetric functions (we compare to and analyze such approaches). Successful formulations have many potential applications, such as structural priors in reinforcement learning (Schaul et al., 2015; Tian et al., 2020),
graph learning (Rizi et al., 2018) and causal relation learning (Balashankar & Subramanian, 2021).
Towards this goal, our contributions are
We study the quasimetric learning task with two goals: (1) fitting training data well and (2) respecting quasimetric constraints (Sec.

---

Published as a conference paper at ICLR 2022
from slate
Datance
Quasimetrics
Metrics
Shorteat Patha Directed Graphs
Euclidean Distance
Hamming Distance
Any Normed Space 1 ---
38
Time Location
Under Gravity
Conditional Entropy
Optimal Bool--laaching Plan Costs MDPs
Gridworld with One-way Doors
Figure 1: Examples of quasimetric spaces. The car drawing is borrowed from Sutton & Barto (2018).
We prove that large family of algorithms, including unconstrained networks trained in the Neural Tangent Kernel (NTK) regime (Jacot al., 2018), fail at this task, while a learned embedding into a latent quasimetric space can potentially succeed (Sec. 4);
We propose Poisson Quasimetric Embeddings (PQEs), the first quasimetric embedding formula- tion learnable with gradient-based optimization that also enjoys strong theoretical guarantees
approximating arbitrary quasimetrics (Sec. 5);
Our experiments complement the theory and demonstrate the benefits PQEs on random graphs, social graphs and offline Q-learning (Sec. 6).
PRELIMINARIES ON QUASIMETRICS AND POISSON PROCESSES
Quasimetric space generalization metric space where all requirements of metrics are satisfied, except that the distances can be asymmetrical.
Definition 2.1 (Quasimetrie Space). A quasimetric space is pair (X' d), where X' is a set of points and d: X x X [0, oo] is the quasimetric, satisfying the following conditions:
Vx, X, Vz,y. X,
x= = d(x: v) =0, (Identity of Indiscernibles) d(x,y) d(y. d(x,2).
(Triangle Inequality)
Being asymmetric, quasimetrics are often thought as (shortest-path distances of some (possibly infinite) weighted directed graph. A natural way to quantify the complexity of a quasimetric is to consider that of its underlying graph. Quasimetric treewidth an instantiation this idea.
Definition 2.2 (Treewidth of Quasimetric Spaces (Mémoli et al., 2018)). Consider quasimetric space M as shortest- path distances on positively-weighte directed graph. Treewidth of M the minimum over all such graphs' treewidths.
Poisson processes are commonly used to model events (or points) randomly occurring across a set A (Kingman, 2005).. c.g., raindrops hitting windshield, photons captured by camera. The number of such events within a subset A is modeled as a Poisson distribution, whose mean is given by a measure j of A that determines how "frequently the events happen each location".
Definition 2.3 (Poisson Process). For nonatomic measure μ on set A, a Poisson process on A with mean measure μ random countable subset P C A (i.c., the random events / points) such that
for any disjoint measurable subsets Ay..... An of A, the random variables N are independent, where (B) e # (P n B} is the number of points of P in B, and
(B)) has the Poisson distribution with mean (BB), denoted as Pois( B)). Fact 2.4 (Differentiabilityy of TP [N(A)) N(A2)). For two measurable subsets A1, A2, P ([N(AA) S N [4)) = P Pois(a(A) \ A2)) < Pois(j((As A2 A1))]
(1)
two independent Poissons Furthermore, for independent X ~ )ois(Mu), Y Pois(u2), the probability IP [X < Y] is differen- tiable w.r.t. μi and μ22 In the special case where la1 or p2 zero, can simply compute
P [0
< Y] =1 X < 0
if fn 0 if μ2
P
(Pois(O) is always 0)
P
=
0] =
= cxp (- (m1 122))
(2)
where + A max(0, 2). For general μl, P2, this probability and its gradients can be obtained via a
connection noncentral x2 distribution (Johnson, 1959). We derive the formulas in the appendix.
Therefore, if A, and A2 are parametrized by some such that μ(A) \ A2)) and 4(A2 A1) are differentiable w.r.t. 0, so is (N(()) & N(A2)).
2

---

Published as a conference paper at ICLR 2022
Train
del Test
Unconstrained Network
Euclidean Space Embedding (Traini ng Arse 55.83 * 0.00)
Poissonn Quasimetric Embedding
(Training Euge 0.02 a 0.066)
(Training Eys: - 0.02 .2 d.07)
100
80
80
Count 60
60-
40
40-
20
Trianglo incquality
? <gd,a,)) + d(b,e) 31
Valid
?> d]a,b) d(c, 28
Range
10 20 20
10
20
30
10
Figure 2: Quasimetric learning on a 3-clement space. Leftmost: Training set contains all pairs except
for (a, c). Arrow labels show quasimetric distances (rather than edge weights). A quasimetric d should predict d((a, e) E [28, 30]. Right three: Different formulations are trained to training pairs distances, and then predict on the test pair. Plots show distribution of the prediction over 100 runs.
QUASIMETRIC LEARNING
Consider quasimetric space (X, d). The quasimetric learning task aims infer quasimetric from observing a training set {< Us. d(r,, 3))) C X' x X' x [0, oo]. Naturally, our goals for a learned predictor d: X' X are: respecting the quasimetric constraints and fitting training distances.
Crucially, we are not simply aiming for the usual sense of generalization, i.e., low population error. Knowing that true distances have a quasimetric structure, we can better evaluate predictors and desire ones that fit the training data and are (approximately) quasimetries. These objectives also indirectly capture generalization because predictor failing either requirement must have large error on some pairs, whose true distances follow quasimetric constraints. We formalize this relation in Thm. 4.3.
3.1 LEARNING ALGORIHHMS AND HYPOTHESIS SPACES
Ideally, the learning should scale well with data, potentially generalize to unseen samples, and support integration with other deep learning systems (e.g.. via differentiation).
Relaxed hypothesis spaces. One can simply learn a generic function approximator that maps the (concatenated) input pair to scalar the prediction of the pair's sii' distance, or its transformed version (e.g., log distance). This approach has been adopted in learning graph distances (Rizi et al., 2018) and plan costs in MDPs (Tian al., 2020). When the function approximator is deep neural network, refer to such methods as unconstrained networks. While they are known to fit training data well (Jacot al., 2), this paper we also investigate whether they learn be (approximately) quasimetrics.
Restricted hypothesis spaces. Alternatively, we can encode each input to a latent space 2, where a latent quasimetric d₂ gives the distance prediction. This guarantees learning quasimetric space X. Often dg is restricted to subset unable to approximate all quasimetrics, i.c., an overly restricted hypothesis space, such as metric embeddings and the recently proposed DeepNorm and WideNorm (Pitis et al., 2020). While our proposed Poisson Quasimetric Embedding (PQE) (specified in Sec. 5) is also a latent quasimetrie, it can approximate arbitrary quasimetrics (and is differentiable). PQE thus searches in space that approximates all quasimetries and only quasimetrics.
data
3.2 A ToY EXAMPLE
To build up intuition on how various algorithms perform according to our two goals, we consider a toy quasimetric space with only 3 elements in Fig. 2. The space has total of 9 pairs, 8 of which form the training set. Due to quasimetric requirements (esp. triangle inequality), knowing distances of these pairs restricts valid values for the heldout pair particular range (which is [28, 31) in this case). If a model approximates training pairs well and respects quasimetric constraints well, its prediction on that heldout pair should fall into this range.
We train three models w.r.t. mean squared error (MSF) over the training set using gradient descent:
Unconstrained deep network that predicts distance,
Metric embedding into a latent Euclidean space with a deep encoder,
Quasimetric embedding into latent PQE space with a deep encoder (our method from Sec. 5).
The three approaches exhibit interesting qualitative differences. Euclidean embedding, unable to model asymmetries in training data, fails attain low training error. While both other methods approximate training distances well, unconstrained networks greatly violate quasimetric constraints; only PQEs respect the constraints and consistently predicts within the valid range.
3

---

Published as a conference paper at ICLR 2022
Here, the structural prior of embedding into quasimetric latent space appears important successful learning. Without any such prior, unconstrained networks fail badly. In the next section, we present a rigorous theoretical study of the quasimetric learning task, which confirms this intuition.
4 THEORETICAL ANALYSIS OF VARIOUS LEARNING ALGORIHTS
In this section, we define concrete metrics for the two quasimetric learning objectives stated above, and present positive and negative theoretical findings for various learning algorithms.
Overview. Our analysis focuses on data-agnostic bounds, which are often of great interests in machine learning (e.g.. VC-dimension (Vapnik Chervonenkis, 2015)). We prove strong negative result for a general family of learning algorithms (including unconstrained MLPs trained in NTK regime, k-nearest neighbor, and min-norm linear regression): they can arbitrarily badly fail to fit training data or respect quasimetric constraints (Thm. 4.6). Our informative construction reveals the core reason of their failure. Quasimetric embeddings, however, enjoy nice properties as long as they approximate arbitrary quasimetrics, which motivates searching for "universal quasimetrics". The next section presents PQEs as such universal approximators and states their theoretical guarantees.
Assumptions. We consider quasimetric spaces (x, d) with X' C R., finite size = | < oo, and finite distances (i.e., d has range [0, oo)). It allows discussing deep networks which can't 't handle infinities well. This mild assumption can be satisfied by simply capping max distances in quasimetrics. For training, m < n² pairs are uniformly sampled as training pairs S C X' x X' without replacement.
In the appendix, we provide all full proofs, further discussions of our assumptions and presented results, as well as additional results concerning specific learning algorithms and settings.
4.1 DISTORTION AND VIOLATION METRICS FOR QUASIMETRIC LEARNING
We use distortion measure of how well the distance is preserved, as standard in embedding
analyses (e.g., Bourgain (1985)). In this work, we especially consider distortion over a subset of pairs, to quantify how well a predictor d approximates distances over the training subset S.
Definition 4.1 (Distortion). Distortion of d over a subset of pairs
X x X' is diss(d) -
Ka.y)
max(r.)) d(z.,)) and its overall distortion is dis(d) e x d(.a))
d(z.y)
For measuring consistency w.r.t. quasimetric constraints, we define the (quasimetric) violation metric. Violation focuses on triangle inequality, which can often be more complex (e.g., in Fig. 2), compared the relatively simple non-nege non-negativity and Identity of Indiscernibles.
Definition 4.2 (Quasimetric Violation). Quasimetric violation (violation for short) of d vio(d) A A(A))Ag)
A, (21.A2)-d(A2.43) where we define for notation simplicity.
Both distortion and violation are nicely agnostic scaling. Furthermore, assuming non-negativity and Identity of Indiscernibles, vio(d) 2 always, with equality iff d is quasimetric.
Distortion and violation also capture generalization. Because the true distance d has optimal training distortion (on S) and violation, a predictor that does badly on either must also be far from truth.
Theorem 4.3 (Distortion and Violation Lower-Bound Generalization Error). For non-negative d, di) 2 max(diss(d), V (d)(,,,, where di) captures generalization over the entire A' space.
4.2 LEARNING ALGORITHMS EQUIVARIANT TO ORTHOGONAL TRANSFORMS
For quasimetric space (X, X C Rdd, we consider applying general learning algorithms by concatenating pairs to form inputs E 2d (e.g., unconstrained networks). While straightforward, this approach means that the algorithms are generally unable to relate the same element appearing as Ist or 2nd imput. As we will show, this is sufficient for a wide family of learning algorithms to fail badly- ones equivariant to orthogonal transforms, which we refer to as OrEq algorithms (Defn. 4.4).
For an OrEq algorithm, training on orthogonally transformed data does not affect its prediction, as long as test data is identically transformed. Many standard learning algorithms are OrEq (Lemma 4.5).
4

---

Published as a conference paper at ICLR 2022
y'
W
x
w
y
y
d(2, 2)
diy, 2)
d(y.
vio(d)
vio(d)
d(sr, y) + dly,z) 2) diss (d)(ssss)))) + d(y, z))
d(y, w) + d(w:;)
2.dis
Training ) 2) = c, d(w, 2) = 1,
Training (-)) d(x, 2) = c, d(w, 2) = 1, d(z, 1/) =1 d(y. w) 1.
d(a.y) v) 1,
d(y, w²) = 1.
Test (- d(y.z)= =?
(-- d(y.2)= =?
Two training sets pose incompatible constraints ( for the test pair distance d(y, z). With one-hot features, an orthogonal transform can exchange (+, y) ++ (*,3²) and (s,w) ++ (*, w ) leaving the test pair (y. 2) unchanged. but transforming the training pairs from one scenario to the other. Given either training set, an OrEq algorithm must attain same training distortion and predict identically on (y, 2). For appropriate c, this implies large distortion or violation in one of these cases.
Figure 3:
Definition 4.4 (Equivariant I Learning Algorithms). Given training set D ((x, y:), C C where 2; are inputs and yi are targets, learning algorithm Alg produces function (D): 2 - Y such that Alg (D)(2)))) is the function's 's prediction on sample z'. Consider T a set of transformations Z + Z. Alg is equivariant to T iff for all transform T E T, training set D, Alg(D) Alg o T,
where TD- = ((T2,)) v): (z, y) E D) is the training set with transformed inputs.
Lemma 4.5 (Examples of OrEq Algorithms). k-nearest-neighhor with Euclidean distance, MLP trained with squared loss in NTK regime, and min-norm least-squares linear regression are OrEq.
Failure case. The algorithms treats the concatenated inputs generic vectors. If a transform fundamentally changes the quasimetric structure but is not fully reflected the learned function (e.g., due to equivariance), learning must fail. The two training sets in Fig. 3 are sampled from two different quasimetrics over the same elements An orthogonal transform links both training sets without affecting the test pair, which is constrained differently in quasimetrics. An OrEq algorithm, necessarily predicting the test pair identically seeing either training set, must thus fail on one. In the appendix, we empirically verify that unconstrained MLPs indeed do fail on this construction.
Extending to larger quasimetric spaces, we consider graphs containing many copies of both patterns in Fig. With high probability, our sampled training fails in the same way-the learning algorithm can not distinguish it from another training set with different quasimetric constraints.
Theorem 4.6 (Failure of OrEq Algorithms). Let (fn),, be an arbitrary sequence of large values. There is an infinite sequence of quasimetric spaces ((An, d,)).. with | n, Nn C RR" such that, over the random training set 5 of size m, any OrEq algorithm must output predictor d that satisfies
d fails non-negativity. or max(diss (d). vio(d) 2 fn (i.e., approximates training S badly or is far from quasimetric), with probability 1/2 - o(1), long S does not contain almost all pairs 1 m/n² = w(n wn/31/3), and does not only include few pairs m/n? = (nnnn//)
Furthermore, standard NTK results show that unconstrained MLPs trained in NTK regime converge function with zero training loss. By the above theorem, the limiting function is not a quasimetric with nontrivial probability. In the appendix, we formally state this result. Despite their empirical usages, these results suggest that unconstrained networks are likely not suited for quasimetric learning.
4.3 QUASIMETRIC EMBEDDINGS
A quasimetric embedding consists of a mapping f from data space X' to latent quasimetric space (Z, dz), and predicts d(z, 3) & d, (f(x), fy)). Therefore, they always respect all quasimetric constraints and attain optimal violation of value 1, regardless of training data.
However, unlike deep networks, their distortion (approximation) properties depend on the specific latent quasimetrics. If the latent quasimetric can generally approximate any quasimetric (with flexible learned encoders such as deep networks), we have nice guarantees for both distortion and violation.
In the section below, we present Poisson Quasimetric Embedding (PQE) as such a latent quasimetric, along with its theoretical distortion and violation guarantees.
5

---

Published as a conference paper at ICLR 2022
5 POISSON QUASIMETRIC EMBEDDINGS (PQES)
Motivated by above theoretical findings, we aim to find latent quasimetric space (IR dz) with deep network encoder f: X + Rd, and quasimetric d, that is both universal and differentiable: for any data quasimetric (X', d), there exists an encoder f such that (x)) f(w)) = d(x, y): d2 is differentiable (for optimizing f and possible integration with other gradient-based systems). Notation 5.1. We use æ, for elements of the data space X' for elements of the latent space Rd, upper-case letters for random variables, and (+), for indicating functions latent space (e.g., dg).
An existing line of machine learning research learns quasipartitions, partial orders, via Order Embeddings (Vendrov al., 2015). Quasipartitions are in fact special cases of quasimetrics whose distances are restricted to be binary. denoted as An Order Embedding is a representation of quasipartition, where OE [r, y) (i.e., is related to y) iff f(x) S f(y) coordinate-wise:
xz, y) n O (f(x,, _
II 1 f0)); f(a),
Order Embedding is universal and can model any quasipartition (see appendix and Hiraguchi (1951)).
Can we extend this discrete idea to general continuous quasimetrics? Quite naīvely, one may attempt a straightforward soft modification Order Embedding:
SoftOE n uu, v) A
II exp (- (uj +t)+t) = - exp -
exeexp
(4)
which equals if u S coordinate- wise, and increases as some coordinates violate this condition more. However, it is unclear whether this gives quasimetric.
more principled way is to parametrize a (scaled) distribution of latent quasipartitions II,, whose expectation naturally gives continuous-valuee quasimetric:
(u, v; II,, a) å a E1,, [ (u, w)],
a 2 0.
(5)
Poisson Quasimetric Embedding (PQE) gives a general recipe for constructing such IT distributions so that dg is universal and differentiable. Within this framework, we will see that n² a quasimetric based on such a distribution and is (almost) sufficient for our needs.
SoftOE is actually
5.1 DISTRIBUTIONS OF LATENT QUASIPARTITIONS
A random latent quasipartition n. quasipartition constraints. Fortunately, the Order Embedding representation (Eq. (3)) is without such constraints. If, instead of fixed latents u, we have random latents R(u), R(v), we can compute:
R + {0, 1} is a difficult object to model, due to complicated
[ [T= (u, w)] (R(W).R()))
(R(w), R(e))] = [R(() & R(v) coordinate-wise) TT OE
(6)
In this view, we represent a random v via a joint distribution of random vectors' {R(u) (R(u))eert huRR,, i.e. a stochastic process. To easily compute the probability of this coordinate-wis wise event, we assume that each dimension of random vectors from an independent process, and obtain
Ex, [u, v)] - II [R,(w) Rz(r).. 3
The choice of stochastic process is flexible. Using Poisson processes (with Lebesgue mean measure; Defn. 2.3) that count random points on half-lines' (-o0, a). we can have Rz(u) = (100,,, uzl). the (random) count of events in (oc, uz] from j-th Poisson process:
Ex,-i (T (u, v)]
II TP ([-,(((-oc,,)) S N₂ (5(((00,,)))) w;))]
(8)
exp ( - (uy - +) = - SoftOE (u, v),
II general, these random vectors R(u) do have he of the same dimension E Rd although the dimensions do match in PQE variants we experiment with. PHalf-lines has I Lebesgue measure oc. More rigorously, consider using small value as the lower bounds of these intervals, which leads same result.

---

Published as a conference paper at ICLR 2022
where used Fact 2.4 and the observation that one half-line is either subset superset of an- other.Indeed =550tEE is an expected quasipartition (and thus a quasimetric), and is differentiable. ==
Considering mixture of such distributions for expressiveness, the full latent quasimetric formula is dQQE-L (u, v; a:)
A Σ 0s exp ( > (uss - ))))
(10)
where we slightly abuse notation and consider latents u and as (reshaped to) 2-dimensional. We will see that this a special PQE case with Lebesgue measure and half-lines, and thus denoted PQE-LH.
5.2 GENERAL PQE FORMULATION
We can easily generalize the above idea to independent Poisson processes of general mean measures M4 and (sub)sett parametrizations Ay(u), and obtain expected quasipartition
E -1. (n) T =
II (A)) = (A)()()))
(11)
j
II P (1s (,)) (ois(us (A,)
(w))))
(12)
Poisson rate of points landing only in A,
which is differentiable as long as the measures and set parametrizations are (after set differences). Similarly, considering mixture gives us an expressive latent quasimetric.
general PQE latent quasimetric is defined with {(us, A.,))., and weights a; as:
PQQE (u, A, & Σ a; E,, 11 (Hi.A.) (u, v)l
(13)
= Σ 0z (1 II Pois(as, (Ar(()) Aiz(u))) & Pois( (Ais(()))) Arr (u)())
whose optimizable parameters include {or)i possible ones from { Ai.j)) (and encoder f)-
This general recipe be instantiated in many ways. Setting Ai,(u) - (-20, [ر,s] and Lebesgue Hi.j recovers PQE-LH. In the appendix, we consider a form with Gaussian- measures and Gaussian-shapes, denoted as PQE-GG. Unlike PQE-LH, PQE-GG always gives nonzero gradients.
The appendix also includes several implementation techniques that empirically improve stability. including learning 0i 's with deep linear networks, formulation that outputs discounted distance, etc.
5.3 CONTINUOUS- STOCHASTIC PROCESSES
But why Poisson processes over more common choices such as Gaussian processes? It turns out that common continuous- valuue processes fail to give differentiable formula.
Consider a non-degenerate process {R(u))u. where ( (R(w), R(v)) has bounded density if u A w. Perturbing u -> u leaves P [ R(u + 5)] 0. Then one of P. P[R(w) S R(u + 5)] and
P R(u + 5) < R(u) must be far away from (as they sum to 1), breaking differentiability at [[((u)= I R(u)] = (This argument is formalized the appendix.) Discrete-valued processes, however, can leave most probability mass R(u)= R(u 8) and thus remain differentiable.
5.4 THEORETICAL GUARANTEES
Our PQEs bear similarity with the algorithmic quasimetric embedding construction in Mémoli et al. (2018). Extending their analysis to PQEs, we obtain the following distortion and violation guarantees.
Theorem 5.2 (Distortion and violation of PQEs). Under the assumptions of Sec. 4, any quasimetric space with size n and treewidth admits a PQE-LH and a PQE-GG with distortion (t n) and violation 1, with expressive encoder (e.g., a ReLU network with 3 layers and polynomial width).
In fact, these guarantees apply to any PQE formulation that satisfies a mild condition. Informally, any PQE with h x & Poisson processes (i.e., h mixtures) enjoys the above guarantees if it can approximate the discrete counterpart: mixtures of h Order Embeddings, each specified with & dimensions. In the appendix, make this condition precise and provide full proof of the above theorem.
7

---

Published as a conference paper at ICLR 2022
Unconstraines Asyen, Product
Heldout MAE
Heldout MSE
10TM
Deeplorm Wid eNomm
Mettic Embesoing
Groundouth
Haufx
20-2
Groundrruth Mards
Heldout
Groundinch
Morif
10m4
10-3
0.0
0.2
2.4
0.0
0.2
0.4
066
0.0
0.2
0.4 2.6
Training Set Fraction
Training Set Fraction
Training Set Fraction
(a) A dense graph.
(b) A sparse graph.
(c) A sparse graph with block structure.
Figure 4: Comparison of PQE and baselines on quasimetric learning in random directed graphs.
6 EXPERIMENTS
Our experiments are designed to (I) confirm our theoretical findings and (2) compare PQEs against a wider range of baselines, across different types of tasks. In all experiments, o d-discounted distances (with y E {0.9, ). and compare the following five families of methods:
PQEs (2 formulations): PQE-LH and PQE-GG with techniques mentioned in Sec. 5.2.
Unconstrained networks (20 formulations): Predict raw distance (directly, with exp
transform, and with (.)² transform) or 7-discounted distance (directly, and with sigmoid-transffrmm). Each variant is run with a possible triangle inequality regularizer
Ex,y, max(0, - ] for each of weights E {0, 0.3, 1,3).
Asymmetrical dot products (20 formulations): On input pair (I. y). encode each into feature vector with a different network, and take the dot product. Identical to unconstrained networks, the output is used in the same 5 ways, with the same 4 triangle inequality regularizer options.
Metric encoders (4 formulations): Embed into Euclidean space, & space, hypersphere with (scaled) spherical distance, or a mixture of all three.
DeepNorm (2 formulations) and WideNorm (3 formulations): Quasimetric embedding meth- ods that often require significantly more parameters than PQEs (often on the order of 10 ~ 10" more effective parameters; see the appendix for detailed comparisons) but can only approximate a subset of all possible quasimetrics (Pitis et al., 2020).
We show average results from 5 runs. The appendix provides experimental details, full results (including standard deviations), additional experiments, and ablation studies.
Random directed graphs. We start with randomly generated directed graphs of 300 nodes, with 64-dimensional node features given by randomly initialized neural networks. After training with MSE on discounted distances, we test the models' prediction error on the unseen pairs (i.e., generalization), measured also by MSE on discounted distances. On three graphs with distinct structures, PQEs significantly outperform baselines across almost all training set sizes (see Fig. 4). Notably, while DeepNorm and WideNorm do well on the dense graph quasimetric, they struggle on the other two, attaining both high test MSE (Fig. 4) and train MSE (not shown). This is consistent with the fact that they can only approximate a subset of all quasimetrics, while PQEs can approximate all quasimetrics.
Large-scale social graph. We choose the Berkeley Stanfford Web Graph (Leskovec & Krevl, 2014) as the reld social graph for evaluation. This graph consists of 685,230 pages as nodes, and 7,600,595 hyperlinks as directed edges. We use 128-dimensional node2vec features (Grover & Leskovec, 2016) and the landmark method (Rizi et al., 2018) to construct a training set of 2,500,000 5,00,000 pairs, and test set of 150,000 pairs. PQEs generally perform better than other methods, accurately predicting finite distances while predicting high values for infinite distances (see Table 1). DeepNorms and WideNorms learn finite distances less accurately here, and also do much worse than PQEs on learning the (quasi)metric of an undirected social graph (shown in the appendix).
Offline Q-learning. Optimal goal-reaching plan costs in MDPs are quasimetries (Bertsekas & Tsitsiklis, 1991; Tian et al., 2020) (see also the appendix). In practice, optimizing deep Q-functions often suffers from stability and sample efficiency issues (Henderson et al., 2018; Fujimoto et al., 2018). As proof of concept, we use PQEs as coal-conditional Q-functions in offline Q-learning, on the grid-world environment with one-way doors built upon gym-minigr et al., 2018) (see Fig. I right), following the algorithm and data sampling procedure described in Tian et al. (2020). Adding strong quasimetric structures greatly improves sample efficiency and greedy planning success rates over popular existing approaches such as unconstrained networks used in Tian et al. (2020) and asymmetrical dot products used in Schaul et al. (2015) (see Fig. 5). As an interesting observation, some metric embedding formulations work comparably well.
Schevalier-Boisveee
8

---

Published as a conference paper at ICLR 2022
Triangle inequality regularizer
MSE 1-diseeunied distances (x:10 ")
Prodiction when true
tree d < oo
d
0.8-
PQE-LH PQE-GG
3,043
1,26
69 20.942
3,909
1.895
101.824
[[success]
Hest Uncostrained Net.
/
2.813
3,086
2.115
2,211
61.371
59.521
0.6
Best Asym. Dot Product
/
48, 102
48 106
2.520 x 110
2,299 x10"
2.679 x x10"1
2,500 x 10
Unconstrained Network
Embredding
7,510
53,850
0.2
Metric Embedding
Dot Product
Best DoepNorm
5.071
2,085
120.045
DeepNorm
Best WideNorm
3,533
1.769
124.688
WideNorm
Table I: Quasimetric learning on large-scale web graph.
Number Training Trajectories
"Best" is selected by test MSE w.r.t. y-discounted distances.
Figure 5: Offline Q-learning results.
RELATED WORK
Metric learning. Metric learning aims to approximate target metric/similarity function, often via a learned embedding into metric space. This idea has successful applications in dimensionality reduction (Tenenbaum et al., 2000), information retrieval (Wang al., 2014), clustering (Xing et al., 2002), classification (Weinberger et al., 2006; Hoffer & Ailon, 2015), etc. While asymmetrical formulations have been explored, they either ignore quasimetric constraints (Oord al., 2018; Logeswaran & Lee, 2018; Schaul et al., 2015), or are not general enough to approximate arbitrary quasimetric (Balashankar Subramanian, 2021), which is the focus of the present paper.
Isometric embeddings. Isometric ddistancepreeserving embeddings is a highly influential and well-studied topic in mathematics and statistics. Fundamental results, such as Bourgain's random embedding theorem (Bourgain, 1985), laid important ground work in understanding and constructing (approximately) isometric embeddings. While most such researches concern metric spaces, Mémoli et al. (2018) study algorithmic construction of a quasimetric embedding via basic blocks called guasipartitions. Their approach requires knowledge of quasimetric distances between all pairs and thus not suitable for learning. Our formulation takes inspiration from the form of their embedding, but is fully learnable with gradient-based optimization over a training subset.
Quasimetrics and partial orders. Partial orders (quasipartitions) are special cases of quasimetrics (see Sec. 5). A line of machine learning research studies embedding partial order structures into latent spaces for tasks such as relation discovery and information retrieval (Vendrov et al., 2015; Suzuki et al., 2019; Hata et al., 2020; Ganea et al., 2018). Unfortunately. unlike PQEs, such formulations do not straightforwardly generalize arbitrary quasimetries, which are more than binary relations. Similar to PQEs, DeepNorm and WideNorm are quasimetric embedding approaches learnable with gradient-based optimization (Pitis et al., 2020). Theoreically, they universally approximates a subset of quasimetrics (ones induced by asymmetrical norms). Despite often using many more parameters, they are restricted to this subset and unable to approximate general quasimetrics like PQEs do (Fig. 4).
IMPLICATIONS
In this work, we study quasimetric learning via both theoretical analysis and empirical evaluations.
Theoretically, we show strong negative results for common family of learning algorithms, and positive guarantees for our proposed Poisson Quasimetric Embedding (PQE). Our results introduce the novel concept of equivariant learning algorithms, which may potentially be used for other learnability analyses with algorithms such as deep neural networks. Additionally, thorough average-case or data-dependent analysis would nicely complement our results, and may shed light on conditions where algorithms like deep networks can learn decent approximations quasimetrics in practice.
PQEs are the first quasimetric embedding formulation that can be learned via gradient-based opti- mization. Empirically, PQEs show promising performance in various tasks. Furthermore, PQEs are fully differentiable, and (implicitly) enforce quasimetric structure in any latent space. They are particularly suited for integration in large deep learning systems, as we explore in the Q-learning experiments. This potentially open the gate many practical applications such as better em- bedding for planning with MDPs, efficient shortest path finding via learned quasimetric heuristics, representation learning with quasimetric similarities, causal relation learning, etc.

---

Published as a conference paper at ICLR 2022
REFERENCES
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.
Brandon Amos, Lei Xu, and J Zico Kolter. Input convex neural networks. International Conference on Machine Learning, pp. 146-155. PMLR, 2017.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 1900.///55, 2019.
Ananth Balashankar and Lakshminarayanan Subramanian. Learning faithful representations of causal graphs. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 839-850, 2021.
Umberto Bertele and Francesco Brioschi. On non-serial dynamic programming. J. Comb. Theory, Ser. A, 14(2):137-148, 1973.
Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595, 1991.
Kenneth P Bogart. Maximal dimensional partially ordered sets hiraguchi's theorem. Discrete Mathematics, 5(1):21-31, 1973.
Béla Bollobás and Bollobás Béla. Random graphs. Number 73. Cambridge university press, 2001.
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46-5,, 1985.
Barry Brown, James Lovato, and Kathy Russell. CDFLIB: library of fortran routines for cumulative distribution functions, inverses, and other parameters, 1994.
Yury Brychkov. On some properties of the marcum q function. Integral Transforms and Special Functions, 23: 178 03 2012. doi: 10. 00.1080/066544492211111 1.55773844
John Burkardt. C++ source code for CDFLIB. https://people. httts:///epple.sc...uu.ee////// htt..//.......eet//bbbtttttt...
src/cdflib/cde hwwhii//ddflbbb.b html, 2021.
Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Directed metrics and directed graph partitioning problems. In SODA, volume 6, pp. 51-60. Siteseer 2006.
Maxime Srevalier-Boivertr Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https://st //gi thub. com/ httm///axmmcb/////m//mmm besll//ggmmminin soym-minigrid, 2018.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Rubinstein. tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67 2005.
Paul Erdós and Alfréd Rényi. On random graphs. i. Publicationes Mathematicae Debrecen, 6: 290-297, 1959.
Stefan Felsner, Ching Man Li, and William T. Trotter. Adjacency posets of planar graphs. Discrete Mathematics, 310(5):009--1104 2010. ISSN 0012-365X.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596. PMLR, 2018.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In International Conference on Machine Learning, pp. 1655-1655 PMLR, 2018.
Amnon Geifiman, Abhay Yaday, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kernels. arXiv preprint arXiv:2007.01580 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864,77 2016.
10

---

Published as a conference paper at ICLR 2022
Peter Grunwald and Paul Vitányi. Shannon information and kolmogorov complexity. arXiv preprint cs/0410002, 2004.
Matthieu Guillot and Gautier Stauffer. The stochastic shortest path problem: a polyhedral combina- torics perspective. European Journal of Operational Research, 158811)44-1158 2020.
Nozomi Hata, Shizuo Kaji, Akihiro Yoshida, and Katsuki Fujisawa. Nested subspace arrangement for representation of relational data. In International Conference on Machine Learning, pp. 4127-411 PMLR, 2020.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pincau. Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Toshio Hiraguchi. On the dimension of partially ordered sets. The science reports of the Kanazawa University, 1(2):77994, 1951.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. International workshop on similarity-based pallern recognition, pp. 84-92. Springer, 2015.
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. arXiv preprint arXiv:2103.10427, 2021.
Piotr Indyk. Algorithmic applications low-distortion geometric embeddings. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 10-33. IEEE, 2001.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.00 075722 2018.
N. L. Johnson. On extension of the connexion between poisson and x² distributions, Biometrika. 46(3/4):352-363, 1959. ISSN 00063444.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematies, 26(189-206):1 1984.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
John Frank Charles Kingman. Poisson processes. Encyclopedia of biostatistics, 6, 2005.
Andrei N Kolmogorov. On tables of random numbers. Sankhyā: The Indian Journal of Statistics, Series A, pp. 369-376, 1963.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: stanford. edu/ June 2014.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. In International Conference on Learning Representations, 2018.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.0399 2016.
I. Mareum. Table of Q Functions. RAND Corporation, Santa Monica, CA, 1950.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3)3555-36., 1999.
Facundo Mémoli, Anastasios Sidiropoulos, and Vijay Sridhar. Quasimetric embeddings and their applications. Algorûthmica, -011))380333824, 2018.

---

Published as a conference paper at ICLR 2022
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. Measurement and Analysis of Online Social Networks. In Proceedings of the Sth ACM/Usenix Internet Measurement Conference (IMC'07), San Diego, CA, October 2007.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 2018.
Giacomo Ortali and Ioannis G Tollis. Multidimensional dominance drawings. arXiv preprint
AXXiv:996.009244 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buu Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp.
2019.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924-1932. PMLR, 2018.
Silviu Pitis, Harris Chan, Kiarash Jamali, and Jimmy Ba. An inductive bias for distances: Neural nets that respect the triangle inequality. arXiv preprint arXiv:2002.05825 2020.
DJ de Price. Networks of scientific papers. Princeton University Press, 2011.
Martin L. Puterman. Markov Decision Processes: Discrete Stochustic Dynamic Progrumming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
Fatemeh Salehi Rizi, Joerg Schloetterer, and Michael Granitzer. Shortest path distance approximation using deep learning techniques. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 1007-1014. IEEE, 2018
Neil Robertson and Paul Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 2013.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pp. 1312-1320. PMLR, 2015.
G. Skellam. The frequency distribution of the difference between two poisson variates belonging to different populations. Journal of the Royal Statistical Society. Series A (General), 109(Pt 3): 296-296, 1946.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume Volume 2, pp. 761-768, 2011.
Ryota Suzuki, Ryusuke Takahama, and Shun Onoda. Hyperbolic disk embeddings for directed acyclic graphs. In International Conference Machine Learning, pp. 6066-6073 PMLR, 2019.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. science, 290/5500):319-2323, 2000.
Stephen Tian, Suraj Nair, Frederik Ebert, Sudeep Dasari, Benjamin Eysenbach, Chelsea Finn, and Sergey Levine. Model-based visual planning with self-supervised functional distances. arXiv preprint vrXiv:2012.15373, 2020.
William T Trotter. Partially ordered sets. Handbook of combinatorics, 1:433-480, 1995.
12

---

Published as a conference paper at ICLR 2022
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. arXiv preprint arviv 151 1.06661, 2015.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Ker,, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020, doi: 10.1038/641592-0199
Jiang Wang. Yang Song, Thomas Leung, Chuck Rosenberg. Jinghin Wang, James Philbin, Bo Chen, and Ying Wu. Learning fine- the-grained image similarity with deep ranking. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1386-1393, 2014.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity the hypersphere. In International Conference Machine Learning, pp. PMLR, 2020.
Kilian Q Weinberger, John Blitzer, and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. In Advances in neural information processing systems, pp. 1473- 1480, 2006.
Eric P Xing, Andrew Y Ng, Michael I Jordan, and Stuart Russell. Distance metric learning with application to clustering with side-information. In NIPS, volume 15, pp. 12, Citeseer, 2002.
13

---

Published as a conference paper at ICLR 2022
APPENDIX
A Discussions for Sec. 2: Preliminaries on Quasimetrics and Poisson Processes
15
A.1 Quasimetric Spaces
15
A.2 Poisson Processes
18
Proofs, Discussions and Additional Results for Sec. Theoretical Analysis of Various Learning Algorithms
20
B.1 Thm. 4.3: Distortion and Violation Lower-Bound Generalization Error
20
B.2 Lemma 4.5: Examples of OrEq Algorithms
21
B.3 Thm, 4.6: Failure OrEq Algorithms
C Proofs and Discussions for Sec. 5: Poisson Quasimetric Embeddings (PQEs)
33
C.1 Non-differentiabiiiy of Continuous- Valued Stochastic Processes
33
C.2 PQE-GG: Gaussian-based Measure and Gaussian Shapes
34
C,3 Theoretical Guarantees for PQEs
35
C.4 Implementation of Poisson Quasimetric Embeddings (PQEs)
40
D Experiment Settings and Additional Results
43
D.I Experiments from Sec. 3.2: A Toy Example
43
D.2 Experiments from Sec. 6: Experiments.
45
14

---

Published as a conference paper at ICLR 2022
A DISCUSSIONS FOR SEC. 2: PRELIMINARIES ON QUASIMETRICS AND POISSON PROCESSES
A.1 QUASIMETRIC SPACES
Definition 2.1 (Quasimetric Space), A quasimetric space is pair (X, d), where X' is set of points and d: X' x X' > [0, oo] is the quasimetric, satisfying the following conditions:
V., X. Vz, v. X,
== = d(r v) = 0,
(Identity of Indiscernibles)
d(r,y) d(y, d(x, 2).
(Triangle Inequality)
Definition A.1 (Quasipseudometrie Space). As further generalization,
say (X, d) is quasipseudometric space if the Identity of Indiscermibles requirement is only satisfied one direction:
Vx,y E X, Vz, V. 2 X,
I x= = d(z, 3) = 0, d(z, + ddy, 2 2(z,2).
(Identity of Indiscernibles) (Triangle Inequality)
A.1.1 EXAMPLES OF QUASIMETRIC SPACES
Proposition A.2 (Expected Hitting Time of Markov Chain). Let random variables (Xt), be Markov Chain with support X. Then (X, dritting) is quasimetric space, where
dhieting( (8, 1) _ E [time to hit / start from s), where we define the hitting time of s starting from to be O.
(14)
Proof of Proposition A.2. Obviously dhitttig is non-negative We then verify the following quasimet- ric space properties:
Identity of Indiscernibles. By definition, we have, Vz,y E X, x + y. dhitting (z, x) = 0
(15)
dnitting (x, y) 2 1.
(16)
Triangle Inequality. For any I, = E X, we have
dhitting (I. u) + chitting (v, 2) E [time to hit y then hit a start from æ]]
(17)
E [tie to hit = start from x)
(18)
chitting (I. z).
(19)
Hence, (X, dhitting) is a quasimetric space.
Proposition A.3 (Conditional Shannon Entropy). Let X' be the set of random variables (of some probability space). Then (X, dn) is a quasipseudometric space, where
dh (X,YY & H(Y X).
(20)
If for all distinct (X, (X,Y) X X, X can not be written (almost surely) deterministic function of Y, then dH) is a quasimetric space.
Proof of Proposition A.3. Obviously du non-negative. We then verify the following quasipseudo-
metric space properties:
Identity of Indiscernibles. By definition, we have, VX,Y EX, (x, H(X X)= 0 (Y, x HY x) 2 0,
(21)
(22)
where is = iff Y is a (almost surely) deterministic function of X.
Triangle Inequality. For any X, Y, E X, we have
du (x,X du dy Z) H(Y X) + H YY)
(23)
2 H(Y X)+ + H(Z) | XY)
(24)
H(YZ |X)
(25)
2 H(( IX)
(26)
=dr(XX 7).
(27)
15

---

Published as a conference paper at ICLR 2022
Hence, (X, dz) is a quasipseudometric space, and quasimetric space when the last condition is satisfied.
Conditional Kolmogorov Complexity From algorithmic information theory, the conditional Kol- mogorov complexity (y z) also similarly measures "the bits needed to create given æ as input" (Kolmogorov, 1963). it also almost quasimetric, but the exact definition affects some constant/log terms that may make the quasimetric constraints non-exact. For instance, when defined with the prefix-free version, conditional Kolmogorov complexity is always strictly positive, even for (xx 2) >> O (Li et al., 2008). One may remedy this with a definition using universal Turing machine (UTM) that simply outputs the input on empty program. But to make triangle inequality work, one needs to reason about how the input and output parts work on the tape(s) of the UTM. Nonetheless, regardless of the definition details, conditional Kolmogorov complexity do satisfy a triangle inequality up to log terms (Grunwald & Vitányi, 2004). So intuitively, it behaves roughly like a quasimetric defined on the space binary strings.
Optimal Goal-Reachin Plan Costs in Markov Decision Processes (MDPs) We define MDPs in the standard manner: M (S, A, R, P:7) (Puterman, 1994), where the state space, the action space, R: S x A + IR is the reward function, P: S x A - A(S) is the transition function (where (S) is the set of all distributions over S), and y E (0, 1) is the discount factor.
We define II the collection of all stationary policies :: S ((A) on M. For a particular policy т II, it induces random trajectories:
Trajectory starting from state E S is the random variable
(s) = ($1, (1,,01,70 82, 02 .2,...);
(28)
distributed as
81
(29)
0: ~ π (+1),
Vi 2 1 Wi 2
(30)
81+1 P(s;,
(31)
Trujectory starting from state-action pair (s, a) E x A is the random variable
(x(s = (51. F1, 82, 02 .2....).
(32)
distributed as
81 =
(33)
a1 = a
(34)
0, (()).
Vi 2 2
(35)
8;41 ~ a(s
2
(36)
Proposition A.4 (Optimal Geal-Reaching Plan Costs in MDPs). Consider MDP M AS,A R, P.)). WLOG, assume that R: S x A - ( (-x,,0 0) has only non-positive rewards (i.e., negated costs). Let X = S (S A). Then (X, daum) and (X, dz)) are quasipseudometricc spaces, where
daum Kammx,,1) (x,1)
A min E [total costs from to y under m] #Ell
(37)
min (e......... )=((()) Eero Leggtchee not reached sf yet (f
if = 8' E
goal is state
minzen ( E,
y = (s' a') ESX
not reached and performed a' yet
goal state-action pair
(38)
and
dr(II v) log, max E [- total costs from to under m TEll
(39)
is defined similarly.
If the reward function is always negative, (X, dau)) and (X,d,) are quasimetric spaces.
16

---

Published as a conference paper at ICLR 2022
Proof of Proposition A.4. Obviously both dsum and dy are non-negative, and satisfy Identity of Indiscernibles (for quasipseudometric spaces). For triangle inequality, note that for each y, we can instead consider alternative MDPs:
y S, modify the original MDP to make s' a sink state, where performing any action yields reward (i.e., 0 cost);
If as' E S A, modify the original MDP such that performing action a' in state s' surely transitions to a new sink state, where performing any action yields reward (i.e., cost).
Obviously, both are Markovian. Furthermore, they are Stochastic Shortest Path problems with no negative costs (Guillot & Stauffer, 2020), implying that there are Markovian (i.e., stationary) optimal policies (respectively w.r.t. either minimizing expected total cost or maximizing expected cos)). Thus optimizing over the set of stationary policies, II. gives the optimal quantity over all possible policies, including concatenation of two stationary policies. Thus the triangle inequality is satisfied by both.
cost).
Hence, (X, dsum) and (X', dy) are quasipseudometric spaces.
Finally, if the reward function is always negative, x + = dsum (2, > 0 and d y) > so (X, dsum) and (X' dy) are quasimetric spaces.
Remark A.5. We make a couple remarks:
Any MDP with a bounded reward function can be modified to have only non-positive rewards by subtracting the maximum reward (or larger);
We have
daum (8, (8,a)) = (8, (s, (s, -R(s,
(40)
When the dynamics is deterministic, dsum = dy. Vy E (0,
Unless y is reachable from with probability under some policy, drum (I, y) 20.
Unless y is unreachable from æ with probability 1 under all policies, dsum (x, 1) co. Therefore, it is often favorable to consider d, types.
In certain MDP formulations, the reward is stochastic and/or dependent the reached next state. The above definitions readily extend to those cases.
7d (().a),)) is very similar to Q-functions except that Q-function applies discount based on time, and ydt, ((s.0).a) applies discount based on costs. We note that a Q-learning-line like recurrence can also be found for dd, ((ea)))))
If the cost is constant in the sense for some fixed 0, R(s,a) c. V(s, a) E S A, then time and cost equivalent up to scale. Therefore, ((s())))))) coincides with the optimal O-functions for the MDPs described in proof, and yd,(5.)) coincides with the optimal value functions for the respective MDPs.
A.1.2 QUASIMETRIC TREEWIDTH AND GRAPH TREEWIDTH
Definition 2.2 (Treewidth of Quasimetric Spaces (Mémoli et al., 2018)). Consider representa- tions of a quasimetric space M as shortest-path distances on a positively-weighter directed graph. Treewidth of M is the minimum over all such graphs' treewidths. (Recall that the treewidth of a graph (after replacing directed edges with undirected ones) is measure of complexity.)
Graph treewidth is standard complexity measure of how "similar" graph is to tree (Robertson Scymour, 1984). Informally speaking, a graph has low treewidth, we can represent as a tree, preserving all connected paths between vertices, except that in each tree node, store small number vertices (from the original graph) rather than just 1.
Graph treewidth is widely used by the Theoretical Computer Science and Graph Theory communities, since many NP problems are solvable in polynomial time for graphs with bounded treewidth (Bertele & Brioschi, 1973).
17

---

Published as a conference paper at ICLR 2022
A.2 POISSON PROCESSES
Definition 2.3 (Poisson Process). For nonatomic measure on set A, a Poisson process on A with mean measure μ random countable subset P A (i.e., the random events / points) such that for any disjoint measurable subsets AI..... A. of A, the random variables N (AA are independent, where (B) - # (P n B} is the number points of P in B, and (B) has the Poisson distribution with mean (BB), denoted Pois(u(B3).
Poisson processes are usually used to model events that randomly happens "with no clear pattern", e.g., visible stars in patch of the sky, arrival times of Internet packages to data center. These events may randomly happen all over the sky / time. To an extent, we can say that their characteristic feature property of statistical independence (Kingman, 2005).
To understand this, imagine raindrops hitting the windshield of a car. Suppose that we already know that the rain heavy, knowing the exact pattern of the raindrops hitting on the left side of the windshield tells you little about the hitting pattern on the right side. Then, we may assume that, as long as we look regions that are disjoint on the windshield, the number of raindrops in each region are independent.
This is the fundamental motivation of Poisson processes. In a sense, from this characterization, Poisson processes are inevitable (see Sec. 1.4 of (Kingman, 2005)).
A.2.1 POISSON RACE PROBABILITY [Pois(u)) I Pois(u2)) AND ITS GRADIENT FORMULAS
In Fact 2.4 we made several remarks on the Poisson race probability, i... for independent X ~ Pois(p1) (A1) ). Y ~ Pois(U2), the quantity P [X s Y.. In this section, detailedly describe how arrived at those conclusions, and provide the exact gradient formulas for differentiating TP [[X < Y] w.r.t. μ1l and //2.
From Skellam distribution CDF to Non-Central x2 distribution CDE. Distribution of the differ- ence of two independent Poisson random variables is called the Skellam distribution (Skellam, 1946), Therefore, P[X < Y] is essentially the cumulative distribution function (CDF) of this Skellam at O. In Eq. (4) of (Johnson, 1959), a connection is made between the CDF of Skellam (11, (12) distribution, and the CDF of non-central x2 distribution (which a non-centered generalization of x2 distribution) with two parameters k > 0 degree(s) of freedom and non-centrality parameter À 2 0): for integer n > 0,
with its parameter being the rate of the two Poissons. That is, X Y Skellam
P [Skellam H2) 2 n] PP NonCentraly" 2n 2p2 2p1],
(41)
degroo(s) of freedom
non-centrality parameter
which can be evaluated using statistical computing packages such as SciPy (Virtanen et al., 2020) and CDFLIB (Burkardt, 2021; Brown al., 1994).
Maacumm-Q-uunceee and gradient formulas. representing the non-central x² CDF as Marcum-Q-functioo (Marcum, 1950). One definition of the Marcum- Marcum-Q-funcee Q-function QM: R x + RRRii in statistics is
To differentiate through Eq. (41), we consider
2 + a²
Qa A
exp
IM-1 dz,
(42)
2
where IM-1 is the modified Bessel function of order M (When M non-integer, we refer readers to (Brychkov, 2012; Mareum, 1950) for definitions, which are not relevant to the discussion
below.) When used in CDF of non-central x2. we have
PP "Noneentraly2(K- (k; A) x]] =1 - -11QQ((V,v5)
(43)
18

---

Published as a conference paper at ICLR 2022
Combining with Eq. (41), and using the symmetry Skellam(/1 P2) for integer n, P + n] P [Skellam(u), u2) S ml
A Skellam(ppg U1), we have,
(44)
[onCentralyy ? (-2n,, 2/11) < 2p12] 1 - P M 11,2 < 2/11]
if < 0
(45)
if 2 0
1 Q-n(v2pi, v (212)
if <
(46)
2n+1 (v 22
if 2 0.
Prior work (Brychkov, 2012) provides several derivative formula for the Marcum Marcum-Q- Q-Function:
For 0, have
(1 (1- Q-n v2
P < Y +
(47)
8p
Q Q (2(222111 v2u2) QQ-+t1 (0-++((2220) (V2 (Eq. (16) of (Brychkov, 2012))
2222)
3
112
e e (2 (Eq. (2) (Brychkov, 2012))
14
P22
(48)
where 16x)(z) (x) I,
) the exponentially-scaled version of I, that computing libraries often provide due to its superior numerical precision (e.g.. SciPy (Virtanen et al., 2020)),
0
(1 (1-Q-l( 10n(VV2pp 2/1,, v 222z)
P P +
(49)
0p1
0pz
mt1
1/2
e (m(itua)) I
n- 12
11
(Eq. (19) (Brychkov, 2012))
=+
P2
e
(vpi - (va)* _ (2/21H22
(50)
For 2 0, we have
0 p xx Y + n|
Qn+i(1 2222 2211
(51)
1lg
n
M1
(11ttaa) I (2
(Eq. (19) of (Brychkov, 2012))
112
n
((VAT - (2
(52)
U12
and,
0
P
X
S
+ +n]
Quti 1 (v 2212 21111
(53)
0h1
0jz
Qn+2( v /2112 v 22 Qu+ily 2/2,, v 22p)
(Eq. (16) of (Brychkov, 2012))
H1
e (artta)) In+1 (n (2/1122))) (Eq. (2) (Brychkov, 2012))
é - ( (2
(54)
Setting gives the proper forward and backward formulas for P [X SV..
19

---

Published as a conference paper at ICLR 2022
B PROOFS, DISCUSSIONS AND ADDITIONAL RESULTS FOR SEC. 4: THEORETICAL ANALYSIS OF VARIOUS LEARNING ALGORIHTMMS
Assumptions. Recall that assumed a quasimetric space, which is stronger than quasipseu- dometric space (Defn. A.I), with finite distances. These are rather mild assumptions, since any quasipseudometric with infinities can always be modified ohey these assumptions by (1) adding small metric (e.g., de (z, y) e cluzy with small 0) and (2) capping the infinite distances to large value higher than any finite distance.
Worst-case analysis. In this work focus the worst-case scenario, is common in standard (quasi)metric embedding analyses (Bourgain, 1985; Johnson & Lindenstrauss, 1984; Indyk, 2001; Mémoli al., 2018). Such results are important because embeddings are often used heuristics in downstream tasks (e.g., planning) which are sensitive to any error. While our negative result readily extends to the average-case scenario (since the error (distortion or violation) arbitrary), we leave a thorough average-case analysis as future work.
Data-independent bounds. We analyze possible data- iatta-indepeddent bounds for various algorithms. In this sense, the positive result for PQEs (Thm. C.4) is really strong, showing good guarantees regardless data quasimetric. The negative result (Thm. 4.6) is also revealing, indicating that a family of algorithms should probably not be used, unless we know something more about data. Data- independent bounds are often of great interest machine learning (e.g., concepts of VC-dimension (Vapnik & Chervonenkis, 2015) and PAC learning (Valiant, 1984)). An important future work is to explore data-dependent results, possibly via defining a quasimetric complexity metric that both friendly for machine learning analysis, and connects well with combinatorics measures such as quasimetric treewidth.
Violation and distortion metrics. The optimal violation has value 1. Specifically, it is 1 iff is a quasimetric on X' (assuming non-negativity). Distortion (over training set) and violation together quantify how well d learns quasimetric consistent with the training data. A predictor can training data well (low distortion), but ignores basic quasimetric constraints on heldout data (high violation). Conversely, a predictor can perfectly obey the training data constraints (low violation), but doesn't t actually fit training data well (high distortion). Indeed, (assuming non-negativity and Identity of Indiscernibles), perfect distortion (value 1) and violation (value 1) imply that d is quasimetric consistent with training data.
Relation with classical in-distribution generalization studies. Classical generalization studies the prediction error over the underlying data distribution, and often involves complexity of the hypothesis class and/or training data (Vapnik & Chervonenkis, 2015; McAllester, 1999). Our focus on quasimetric constraints violation is, in fact, not an orthogonal problem, but potentially a core part of in-distribution generalization for this setting. Here, the underlying distribution supported on all pairs of X x X. Indeed, if a learning algorithm has large distortion, it must attain large prediction error on C X X:; if has large violation, must violates the quasimetric constraints and necessarily admits bad prediction error on some pairs (whose true distances obey the quasimetric constraints). Thm. 4.3 (proved below) formalizes this idea, where we characterize generalization with the distortion over all possible pairs in X x X.
B. THM. 4.3: DISTORTION AND VIOLATION LOWER-BOUND GENERALIZATION ERROR
Theorem 4.3 (Distortion and Violation Lower-Bound Generalization Error). For non-negative
d, dis(d) 2 max(diss(d)) / vio())), where dis(d) captures generalization over the entire X' space.
B. PROOF
Proof of Thm. 4.3. is obvious that
dis(d) 2 diss(d).
(55)
Therefore, it remains show that dis(d) V vio(d))
20

---

Published as a conference paper at ICLR 2022
WLOG, say vio(d) 1. Otherwise, the statement is trivially true.
By the definition of violation (see Defn. 4.2), have, for some æ, U. X, with d(xr,2) 0,
d(z, 2) d(x, u) + d(y,z)
vio(d).
(56)
If d(æ, v) d(y, z) = 0, then we must have one of the following two cases:
d(z, y) or d(y, 2) > O, the statement is true because dis (d) = oc.
If (fd(z d(y, 2) 0, then d(ær, =) and the statement is true since dis(d) 2 d(a.))
2(x.z)
oC.
is sufficient to prove the case that d((x, v) + d(y, =) > 0. We can derive
d(x, 2) vi)(d) (d(z, + d(v: z)
(57)
vio (d(z,)) v) + d(y, 2)
(58)
dis(d)
vio(d) d(x, 2).
(59)
dis(d)
ded z) = 0, then dis(d) oo and the statement is trivially true.
If d(x, x) 0, above Eq. (59) implies
dis (d) 2 d(x, =)
vio(d) dis(d) 2 v vio(d). d(x, dis(d)
(60)
Combining Eqs. (55) and (60) gives the desired statement.
B.2 LEMMA 4.5: EXAMPLES OF OREQ ALGORITHMS
Lemma 4.5 (Examples of OrEq Algorithms). k-nearest-neiihhoo with Euclidean distance, MLP trained with squared loss NTK regime, and min-norm least-squares linear regression are OrEq.
Recall the definition of Equivariant Learning Transforms.
Definition 4.4 (Equivariant Learning Algorithms). Given training set D = [(x, w)) C 2 x where 2, are inputs and y; are targets, learning algorithm Alg produces function Alg(D): Y such that Alg (2"")) is the function's 's prediction sample z'. Consider T set of transformations Z Z. Alg is equivariant to T iff for all transform E TT, training set DD Alg(D) Alg(TD)) o T, where TD ((T2, y): (2,y) v) E D) is the training with transformed inputs.
B.2.1 PROOF
Proof of Lemma 4.5. We consider the three algorithms individually:
k-nearest neighbor with Euclidean distance.
It is evident that a learning algorithm only depend on pairwise dot products (or distances), it is equivariant to orthogonal transforms, which preserve dot products (and distances). k-nearest- neighbor with Euclidean distance only depends on pairwise distances, which can be written in terms dot products:
- - = 2x Txy
(61)
Therefore, it is equivariant to orthogonal transforms.
Min-norm least-squares linear regression.
Recall that the solution to min-norm least-squares linear regression Ar is given by Moore-Penrose pseudo-inverse b For any matrix A E RRmx with SVD UEV* A,
21

---

Published as a conference paper at ICLR 2022
and T E ((n) (where (n)) is the orthogonal group in dimension n)), we have
(AT') ) (UEV*T")* TV - where we used T = 7 for T (n)). The solution for the transformed data AT and b is thus
(62)
(AT = TA+b.
(63)
Thus, for any new data point e R and its transformed version Tā R",
(T (AT))= = TTT = iA-
(64)
transformed problem prediction
original problem prediction
Hence, min-norm least-squares linear regression is equivariant to orthogonal transforms.
MLP trained with squared loss in NTK regime.
We first recall the NTK recursive formula from (Jacot et al., 2018).
Denote the NTK for a MLP with L layers with the scalar kernel ( R& x Rd + R. Let B > be the (fxeed parameter for the bias strength in the network model, and a be the activation function. Given E Rd it can be recursively defined as following. For h E [Z],
(x,) 2) - ((h
(x, (r, (x, (a,,),
(65)
where
LT
)00) (x,2) d" z=²² 2+ 82,
(66)
Σ(h (x, 2)
101-1) (x,2) EE(-1) (2,
(67)
5th (z,
(x, 2) = =c =c B(u.)) [d())(v)) +.3
(68)
(x0 2) =c =c- C.EB(un)-N (()))(u)),
(69)
for some constant c.
It is evident from the recursive formula, that ( 2) only depends on x z and x 2z. Therefore, the NTK is invariant to orthogonal transforms.
Furthermore, training an MLP in NTK regime is the same kernel regression with the NTK (Jacot et al., 2018), which has a unique solution only depending on the kernel matrix on training set, denoted as Kirain E Ra where is the training set size. Specifically, for training data (1
y:) [x)]) the solution fNTK: : - IR can be written as
fNTK (x) = (0(L) (r,01) (1,
... (x,) Krriin,,
(70)
where y = (y1
y2
yn) is the vector of training labels.
Consider any orthogonal transform T' E O(d), and the NTK regression trained on the transformed
data {(Tx,, hejnj- Denote the solution as JNTK,T: : R + R. As we have shown, K is invariant such transforms, and remains the same. Therefore,
JÑTK.T(Ta) = Txi) (Tx,TTTTe)))
( (Tx, K Trainn
(71)
= (x,())x) ((1(2,))))
(x, Kirin
(72)
= =fT
(73)
Hence, MLPs trained (with squared loss) in NTK regime is equivariant to orthogonal transforms.
Furthermore, we note that there are many variants of MLP NTK formulas depending on details such as the particular initialization scheme and bias settings. However, they usually only lead slight changes that do not affect our results. For example, while the above recursive NTK formula are derived assuming that the bias terms are initialized with a normal distribution (Jacot al., 2018), the formulas for initializing bias as zeros (Geifman et al., 2020) does not affect the dependency only dot product, and thus our results still hold true.
These cases conclude the proof.
22

---

Published as a conference paper at ICLR 2022
N¹'
1
W
W
w
2
w
d(.. 2 diss (d)(sss d(v. =))
diy. 2 d(y.=)
vio(d)= 2
vio(d) 2 d(y. w) d(w,z)
d(a,8) 1 d(y. 2)
2 ddss((d)
Training (-+): d(z,z) 2) C, d(w, 1, d(y, w') 1.
Training d(z,2) - c, d(w, 2) 1, d(x,1/ ))=== 1, d(y. w) 1.
d(w,z) v) 1,
Test :- d(y. 2)
Test (--+): d(y.z)=?
Figure 6: Two training sets pose incompatible constraints for the test pair distance d(y, 2).
With one-hot features, an orthogonal transform can exchange (*, y) ++ (v, 3/) and (+, w) ++ (*, w leaving the test pair (y. 2) unchanged, but transforming the training pairs from one scenario to the other. Given either training set, an OrEq algorithm must attain same training distortion and predict identically on (y, =). For appropriate c, this implies large distortion violation in one of these cases.
B.3 THM. 4.6: FAILURE OF OREQ ALGORIHTM
We start with a more precise statement of Thm. 4.6 that takes into consideration divergent m/n²: Theorem 4.6 (Failure of OrEq Algorithms). Let (fn),, be an arbitrary sequence of large values. There is an infinite sequence of quasimetric spaces ((A,, d,,),. with |x,]] n, Nn C IR" such that, over the random training set S of size m, any OrEq algorithm must output predictor d that satisfies d fails non-negativity, or max(diss (d), vio(d) 2 fn (i.e., d approximates training S badly or is far from quasimetric), with probability 1/2 o(1), long S does not contain almost all pairs m/n² w(n wn13)/3),
and does not only include few pairs m/n? = w(n wnn-1/2).
Recall that the little-Omega notation means f = w(g) - g o(f.)
B.3.1 PROOF
Proof strategy. In our proof below, we will extend the construction discussed Sec, 4.2 to large quasimetric spaces (reproduced here Fig. 6). To do so, we
1. Construct large quasimetric spaces containing many copies of the (potentially failing)
structure in Fig. where we can consider training sets of certain properties such that
we can pair up such training sets,
an algorithm equivariant orthogonal transforms must fail on one of them, for each pair, the two training sets has equal probability of being sampled: Then, it remains to show that with probability 1 o(1) we end up with a training set of such properties.
2. Consider sampling training set as individually collecting each pair with a certain probability p. and carefully analyze the conditions to sample a training set with the special properties with high probability 1 o(1).
3. Extend to fixed-size training sets and show that, under similar conditions, we sample a training set with the special properties with high probability 1 o(1).
In the discussion below and the proof, we will freely speak infinite distances between two elements of X but really mean a very large value (possibly finite). This allows to make the argument clearer and less verbose. Therefore, we are not restricting the applicable settings of Thm. 4.6 to quasimetrics with (or without) infinite distances.
In Sec. 4.2, showed how caaiiigonn--transfoo----eee differently for the two particular quasimetric spaces and their training sets shown in Fig. 6.
algorithms can not predict d(y, 2)
But are these the only bad training sets? Before the proof, let consider what kinds of training sets are bad for these quasimetric spaces. Consider the quasimetries dust and dright over X
23

---

Published as a conference paper at ICLR 2022
{x. y. 3 2, w, w'), with distances as shown in the left and right parts of Fig. 6, where we assume that the unlabeled pairs have infinite distances except in the left pattern d(z, ) S 2, and in the both patterns d(y, 2) has some appropriate value consistent with the respective triangle inequality.
Specifically, we ask:
For what training sets Sieft C A' x A' can we interchange ++ y/ and w ++ w' on 2nd input to obtain a valid training set for dright, regardless of c?
For what training sets Sright C X' X' obtain a valid training set for diett regardless of c?
interchange y + s/ and w' 2nd input to
Note that if Siet (or Sright) satisfies its condition, the predictor from an algorithm equivariant to orthogonal transforms must (1) predict d(y. z) identically and (2) attain the same training set distortion on it and its transformed training set. As we will see in the proof for Thm. 4.6, this implies large distortion or violation for appropriate
Intuitively, all we need is that the transformed data do not break quasimetric constraints. However, its conditions are actually nontrivial as we want to set e to arbitrary:
We can't have (x, w) Srigtt because it would be transformed into (z, w) which has (2, (2, w) I 2. Then diight(z, w) < and then restricts the possible values of c due to tri- angle inequality with dright W, 2) 1. For similar reasons, can't 't have (z, w') Steft In fact, we can't 't have a path of finite total distance from x to w (or w') in Stight (or Siett).
We can not have (y'. y') E (()) (which has distance 0), which would get transformed into (y/, y) with distance O, which (on the right pattern) would restrict the possible values of c due to triangle inequality, and break our assumption of d(.) not being a quasipseudometric. For similar reasons (w', w'), and cycles containing y' or w' with finite total distance, should be avoided.
We note that having (y.y) y) or (w, w) would also break the non-quasipseudometii assumptions, and thus should avoid them as well (although cycles are okay here since they do not restrict values of c). In fact, with metrics more friendly to zero distances (than distortion and violation, which are based on distance ratios), might be possible to allow them and obtain better bounds in the second-moment argument below in the proof for Thm. 4.6.
Similarly, we can't have V'). (v', v), (we w'), or (w', w) in S(), as they will be mapped to (y, v).(s' v'), (w, w), or (w', w').
With these understandings of the pattern shown in Fig. 6, we are ready to discuss the constructed quasimetric space and training sets.
Proof of Thm. 4.6. Our proof follows the outline listed above.
Construct large quasimetric spaces containing many copies of the (potentially failing) structure in Fig. 6.
For any n. > O, consider the following quasimetric space (X,, d,) of size n, with one-hot features. WLOG, assume n = 12k is multiple of 12. If it is not, set at most 11 elements to have infinite distance with every other node. This won't affect the asymptotics. Let the n = 12k elements of the space be
Xx = [Z left ..... Thk
left
right
right left
left
right
right k
2k right
Wk
left
left
right
Alft
left right
right
vi ..... Uk
1/1
3/
w
wk
W22
Mete ..... I Meet
right
.... Vos
right
,1, 2k: 2k-1....5 22h )
(74)
24

---

Published as a conference paper at ICLR 2022
with quasimetric distances, Vi, J.
dn (ar left : 22) = d=;= right
-2))
(75)
d, (w lott 22) dn dw (w .2))
(76)
dn (=) left) = dn (x right yright
= 1
(77)
d, (w) wffftt
(V: right
right
(78)
dn (x) w. f = 2
(79)
dn (v left =z) =
(80)
dn (v) right .=z)= 22
(81)
where subscripts are colored to better show when they are the same (or different), unlisted distances are infinite (except that d, d,, u) = 0, Vu E X). Essentially, we equally divide the 12k nodes into "types", fz, y. w, 2, w', y corresponding to the nodes from Fig. where each type has half of its nodes corresponding to the left pattern (of Fig. 6), and the other half corresponding to the right pattern, except for the z types.
Furthermore,
Among the left-pattern nodes, each with the same subscript are bundled together in the sense that अ. only has finite distance to y which only has finite distance to w/llftt (instead of other yf or wt ()f 's). However, since distance to/from y! and wleft are infinite anyways,
pair (n//eft, yl wfffff sfett w. 2n.)
(82)
for any i,j, h, to obtain a left pattern.
Among the right-pattern nodes, each set with the same subscript are bundled together in the sense that right only has finite distance to y, rright and y/, fight which only has finite distance to w. right (instead of other y/ trightss 's w wigghts)) s). However, since are distances are infinite anyways. we can pair
right
(a (igight rright right right right
Yi
wi 2%h
(83)
for any 1, h, to obtain a right pattern.
We can see that (X, indeed satisfies all quasimetric space requirements (Defn. 2.1), including triangle inequalities (e.g., by, for each (a, b) with finite distance d, (a, b) oc, enumerating finite finite-length paths from to b).
Now consider the sampled training set S.
We say S is had on a left pattern specified by hetts Jiefts leett hiett if
S 3 ((x//et Flua ), (sr Jnft), Jaftt wofeft) (wlen, =taa)
(84)
@ = S n { (eft =2mmn) ), left Jeft), ), (wifft wleft) ) (y/enn s/een) ), flet
welltt
he Aeft
left (2r ) (y/ete Meft)) (wolett u ( (oftet vlaft) (wiah left))
(85)
We say S is bad on right pattern specified by iright, Frights dright, Bright, if right
right S 3 (irtishtt Fhing) brats (right) ), (yrrighe -. rightt (W Rhigg)) }
(86)
0 = S n (1
Jran Bhugan ), (1 (iright right). (w right rigghtt) (iiright (rright)) (woygn w. rright right (ar (Ir W ), (y
right
rightt
right rright, ( right
Whag (right) rright right) ) (w (w/ngg u
righht right
mnate )
(Urress Poaes::nnna
(Wina
(87)
Most importantly,
If S is bad on a left pattern specified by iiett Stetty leets higts consider the orthogonal transform that interchanges yeft <>> y and weeet <> fffeet on 2nd input. In S, the
25

---

Published as a conference paper at ICLR 2022
possible transformed pairs
d(aiin Mica!
=
d(
a Alftt)
= 1,
(known in S)
d(viun left
Wine
=
d(y
left left)
1,
(known in S)
d(u, yaicn)
00
d(u, jin oc,
(poissble in S for some u # x!lftt
d(u, slah))
= 00
left d(u, Mise oc,
(poissble in S for some u)
d( u. Whee
d(u,, wlftt)
oc, (poissble in S for some & ( juft) 1)
d(u, with
00
d(u,
10 llftt)
oc.
(poissble in S for some u)
The crucial observation is that the transformed training set just look like one sampled from quasimetric space where
the quasimetric space has one less set of sett-paterm elements, the quasimetric space has one more set of right- pattern elements, and transformed training set is bad on that extra right pattern (given by the extra set of right-pattern elements),
which can be easily verified by comparing the transformed training set with the require- ments Eqs. (86) and (87).
Similarly, if is bad on a right pattern specified by fright: Jrights lights hrights consider rright and w right ts w rright on 2nd
the orthogonal transform that interchanges jiigtt input. In S the possible transformed pairs are
right
++ Vinger
Ligh
rright d ((at Minga =
d( vight) = 1,
(known in S)
d( Jane w )
right
=1
d(y diyaam
right
rright = 1,
(known in S)
d( u, jigu
right
= oc
d(u, Vinga
rright = oo,
(poissble in S for some u)
d( u. Hinge
rright) 0C
right oo, d(u, u, Manee
(poissble in S for some u + right
ingh
d(u, tright)
xC
d(u,
wo Srgtee
right
= 00;
(poissble in S for some w.)
d(u, w
Jagn
right x
d(u, Wigg 0o.
rright
right (poissble in S for some u & (Tag Migh })
Again, the crucial observation is that the transformed training set just look like one sampled from quasimetric space where
the quasimetric space has one less set of right-pattern elements, the quasimetric space has one more set of left-pattern elements, and transformed training set is bad on that extra left pattern (given by the extra set of left- pattern elements),
which can be easily verified by comparing the transformed training set with the require- ments in Eqs. (84) and (85).
Therefore, when S is bad on both left pattern and right pattern (necessarily disjoint sets of pairs), we consider the following orthogonal transform composed of:
(a) both transforms specified above (which only transforms 2nd inputs),
(so that after this we obtain another possible training set of same size from the quasi- metric space that is only different up some permutation of X))
(b) a permutation of X (on both inputs) so that the bad left-pattern nodes and the bad right- patterm nodes exchange features,
This transforms gives another possible training set of same size from the same quasimetric space, also is bad left pattern and right pattern. Moreover, with particular way of select bad patterns (e.g.. by the order of the subscripts), this process is reversible. Therefore, we have defined way to pair up all such bad training sets.
26

---

Published as a conference paper at ICLR 2022
Consider the predictors dbefore and dater trained these two training sets (before and after transform) with an learning algorithm equivariant to orthogonal transforms. Assuming that they satisfy non-negativity and Identity of Indiscernibles, we have,
The predictors have the same distortion over respective training sets.
Therefore we denote this distortion as diss(d) without specifying the predictor d or training set
the predictors must predict the same on heldout pairs in the sense that
( 2howe) = datter Ingn Aeeeggee )
right
(88)
right diefore (Vinnn Zhhiggee ) = datter WVinn 2hmm ).
left
(89)
Focusing on the first, we denote
d(y, 2) 2 dibefore (V Ahrnn) = dattor (V right
(90)
without specifying the predictor d the specific y and 2.
However, the quasimetric constraints on heldout pairs (u 2loee) and WWiam Shign completely different (see the left vs. right part of Fig. 6). Therefore, as shown in Fig. assuming non-negativity, one of the two predictors must have total violation at least
right
d(y,2)
vio(d) 2 max
(91)
(iss (d) + d(y, 2 diss(d)
Fixing a large enough c, two terms in the max of Eq. (91) can equal for some d(y, z), and are respectively decreasing and increasing in d'y, z). that case, we have
8
vio(d) 2 2 (is)
(92)
for > such that
5
(93)
(dss + 6)
2 (d)
Solving the above quadratic equation gives
diss(d) + diss (d)² + 8c
(94)
2
leading
-1 v (c/dis
vio(d) 2
(95)
4
Therefore, choosing 2 f2f4 + 1)² gives
diss (d) S fn
(96)
-1 v + (d)d
vio(d)
(97)
- -1+ + I + ff2 + 1)2/83
(98)
-1+ + 8(4f + 1)3
(99)
1 + 4fn +1
(100)
4
= =
(101)
Hence, for training sets that are bad on both a left pattern and a right pattern, we have shown a way to pair them up such that
each pair of training sets have the same size, and the algorithm fail one of each pair by producing a distance predictor that
27

---

Published as a conference paper at ICLR 2022
has either distortion training set 2 fn, violation 2 fu. and has test MSE
Jn.
Remark B.1. Note that all training sets of size has equal probability of being sampled. Therefore, to prove the theorem, it suffices show that with probability o(1), ) we can sample training set of size m that is bad on both a left pattern and a right pattern.
2. Consider sampling training set as individually collecting each pair with certain prob- ability p, and carefully analyze the conditions to sample training with the special properties with high probability - =([).
In probabilistic methods, it is often much easier work with independent random variables. Therefore, instead of considering uniform sampling a training set S of fixed size m, we consider including each pair with probability p. chosen independently. We will first show result based on this sampling procedure via second moment argument, and later extend to the case with a fixed-size training set.
First, let's define some notations that ignore constants:
5~g ʃ f= و
(102)
- - f= f=
(103)
We start with stating a standard result from the second moment method (Alon & Spencer, 2004).
Corollary B.2 (Corollary 4.3.5 of (Alon & Spencer, 2004)). Consider random variable X X1 + X2 + .... + X,, where X, is the indicator random variable for event A,. Write i~ j and the pair of events (A,, Aj) are not independent. Suppose the following quantity does not depend on i:
P[Ay A4).
(104)
j-i
[ + Do and A < E [X], then X
EE
[X] with probability 1 1 o1).
We will apply this corollary obtain conditions on such that S with probability (11) is bad on some left pattern, and conditions such that S with probability - o(1) bad on some right pattern. union bound would then give the desired result.
S is bad on some left pattern.
Recall that left pattern specified by leftt Jieft, Hefty hert all E [k]]
(a Menn Wan U/ua when #hua)
Jeft Aeft Aleft
left
(105)
Therefore, we consider k1 = ( events of the form
Aigaciinnchuneean (S is bad on the left pattern at ieett fiett, Hetty Mete
(106)
Obviously, these events are symmetrical, and the A Eq. (104) does not depend on i.
By the quasimetric space construction and the requirement for S to be bad left pat- tern in Eqs. (84) and (85), we can see that (Metes Jtett: left. Meett ~ Keet Kens K(e)) only if reett Vio fiett Heft lift lett or hieet Mant-
28

---

Published as a conference paper at ICLR 2022
Therefore, we have
E [ p (L-
(include pairs & exclude 10 pairs)
A < (1
(share fleft)
(1²p2(1-p)"
(share ilftt
+n²p'(1-7 pp) p)
(share leftt)
+n²p²(1-p) pp
(share /1jott)
+n²p²(1 p)4
(share jieft: Heft)
+n²p¹(1- (1-1) p)*
(share jieft hiet)
+n²p²(1 p)
(share Jieft: heett
+n²p²(1- -pp" 4p)
(share újefts Mefe)
+n²p(1-1) -p)
(share Rette Hiftt
+n²p((1-p)) p)
(share lieft Hijeft
+n(1-p²
(share itefts liett heftt
+ + (1-p) p)*
(share jieft liett hlert
+ + p)3
(share jiete, Hefee heet)
+ n (1-p)
(share Jieft diefts 4ett)
n p1 p)7 + nn²(p² -p) + + p)))
(107)
+ nn(1 p)3 xp² p²(11 p)).
(108)
Therefore, to apply Corollary B.2, we need to have
p²t (1 p)
(109)
n²'²(1 - p)² < n1 10
(110)
n (1 -1-1()))) < n'p'(1 -1) 10
(111)
m((1 - p)8 1²(1 p)) < (1'p((1-1) 1)
(112)
which gives
p> 1/2
1/2
(113)
> n 1/3
(114)
as a sufficient condition to for S to be bad on some left pattern with probability o(1)..
S is bad on some right pattern.
Recall that right pattern is specified by rright, Fright: frghtt, Bright all [k]] right
(x. (3r y Uinnn Miaae w0 Jrats w/ Legia Fhigue)
rright
right
right righht
(115)
Similarly, we consider 1 = -2z events of the form
A digur digte hiigh {S is bad on the left pattern at frihhts Frights Frihtts hrihht (116)
Again, these events symmetrical, and A in Eq. (104) does depend on i.
29

---

Published as a conference paper at ICLR 2022
Similarly, we have
E [ p (1-)'
(include pairs & exclude 10 pairs)
A <
(1
(share iright)
(1'p"(1-p)
(share Fright)
(1-p((1p))"
(share hright)
(1pp((1p))
(share Light)
+n²p²(1 p)4
(share fright: Jright)
+1²p²(1 101--p1 p)
(share Wright Aright)
+n²p²(1 p)*
(share fright Frihht)
+n²p²(1 p)²
(share Fright: Hright)
+1²p0(1 - p)s
(share jright Aright)
+n²p²(1-1 - p)
(share hright Fight)
+ +1p2(1 pp) p)
(share jright; Brightt Fightt
+ +np (1-p) p))
(share dright: hright, Fight)
n1p (1)p)
(share fright, Jright Iright)
+ +n(1- p)
(share frights Fright: Nright)
n pp p)* + + +²²p² p)*
(117)
+ +n(1 p).
(118)
Therefore, to apply Corollary B.2, we need to have
n n²p' 11 p) 10
(119)
n² n² p)* < nn p))
(120)
n n²p²(1 (1 - p)¹ < (1-))
(121)
n(1 p) < n'p n1p²(11 -1-1p)) -p)
(122)
which gives
p >> n 3/4
(123)
1 > n 1/3
(124)
as sufficient condition to for S to be bad on some right pattern with probability o11)
So, by union bound, long as
p >> n 1/2
(125)
p 1/3
(126)
S is bad on some left pattern and some right pattern with probability 1- o())
3. Extend to fixed-size training sets and show that, under similar conditions, sample
a training set with the special properties with high probability 1 - o1).
To extend fixed-size training sets, we consider the following alteration procedure:
(a) Sample training set by independently include each pair with probability p & mit for some > 0.
(b) Show that with high probability 1 - o()), we end up with [m, m + 26) pairs in S.
(c) Make sure that p satisfy Eq. (125) and Eq. (126) so that S is bad on some left pattern and some right pattern with high probability
o(1).
(d) Randomly discard the additional pairs, and show that with high probability 1 - o(1) this won't affect that S is bad on some left pattern and some right pattern.
We consider each step in details:
30

---

Published as a conference paper at ICLR 2022
(a) Sample training set S by independently include each pair with probability p - m for some > O.
For p the number of pairs in the training set is distributed
m+6
Binomial(n?, m + 6 ) n (b) Show that with high probability 1 o(1), we end up with [m, m + 26] pairs in S. Standard Binomial concentration tells us that,
(127)
8 > ny p(1 p) P Binomial(n", m +
$ [m, + +2]]
- 0, (128)
n
which can be satisfied if
>>
(129)
(c) Make sure that satisfy Eq. (125) and Eq. (126) so that S is bad on some left pattern and some right pattern with high probability o(1). Therefore, want
m +
>> 1/2
(130)
n²
1 m7 +
>> 1/3
(131)
n²
(d) Randomly discard the additional pairs, and show that with high probability o(1) this won't affect that S is bad some left pattern and some right pattern. Consider any specific bad left pattern and right pattern in S. It is sufficient that don't break these two patterns during discarding.
Since we only discard pairs, suffices to only consider the pairs we want to preserve, which are total of 8 pairs across two patterns.
Each such pair is discarded the probability S 26 since remove at most 26 pairs. By union bound,
165
IP [all 8 pairs are preserved] >
(132)
m
Hence, it suffices to make sure that
8 <
(133)
Collecting all requirements, we have
5 >>> n
(134)
m + 6
> n 1/2
(135)
n²
+ 8 n²
n 1/3
(136)
8 < m.
(137)
Assume that
m >> 11 1/2
(138)
n²
m n2 1/3
(139)
n²
It can be easily verified that using 8 A n.
satisfies all conditions.
Hence, for a uniformly randomly sampled training set S with size m, S is bad on some left
pattern and some right pattern with high probability o(1), as long
m 1/2
n1
(140)
n
m > n 1/3
(141)
n²
This is exactly the condition we need to prove the theorem (see Remark B.
This concludes the proof.
31

---

Published as a conference paper at ICLR 2022
B.3.2 DISCUSSIONS
Training set size dependency. Intuitively, when the training set has almost all pairs, violation can be lowered by simply fitting training set well; when it is small and sparse, the learning algorithm may have an easier job finding some consistent quasimetric. Thm. 4.6 shows that, outside these two cases, algorithms equivariant to orthogonal transforms can fail. Note that for the latter case, Thm. 4.6 requires the training fraction to decrease slower than n n-122, which rules out training sizes that is linear n. We leave improving this result as future work. Nonetheless, Thm. 4.6 still covers common scenarios such as fixed fraction of all pairs, and highlights that training caatinggdttt-aann -ata-aggooticc result (such as the ones for PQEs) is not possible for these algorithms.
Proof techniques. In embedding theory, it is quite standard to analyze quasimetrics directed graphs due their lack of nice metric structure. In the proof for Thm. 4.6, we used abundant techniques from the probabilistic method, which are commonly used for analyzing graph properties the asymptotic case, including Corollary B.2 from the second moment technique, and the alteration technique to extend to fixed-size training sets. While such techniques may be new in learning theory, they are standard for characterizing asymptotic probabilities on graphs, which quasimetrics are often analyzed as (Charikar al., 2006; Mémoli al., 2018).
To provide more intuition on why these techniques are useful here, we note that the construction of training set of pairs is essentially like constructing an Erdös-Rénn Rényi random graph n² vertices. Erdös-Rény' (undirected) random graphs come in two kinds:
Uniformly sampling a fixed number of m edges;
Adding an edge between each pair with probability p, decided independently.
The latter, due its independent decisions, is often much easy to analyze and preferred by many. The alteration technique (that we used in the proof) also a standard way to transfer a result on a random graph of the latter type, random graph of the former type (Bollobás & Béla, 2001). Readers can refer to (Alon & Spencer, 2004; Bollobás & Béla, 2001; Erdös & Rényi, 1959) for more in-depth treatment of these topics.
Generalization to other transforms. The core of this construction only relies on the ability to swap (concatenated) inputs between (x, v) + (z, y') and between (y, w) <> (y. w') via transform. For instance, here the orthogonal transforms satisfy this requirement on one-hot features. Therefore, the result also be generalized other transforms and features with the same property. Our stated theorem focuses on orthogonal transforms because they correspond to several common learning algorithms (see Lemma 4.5). If a learning algorithm is equivariant to some other transform family, would be meaningful to generalize this result to that transform family, and obtain similar negative result. We leave such extensions as future work.
B.3.3 COROLLARY OF DISTORTION AND VIOLATION FOR UNCONSTRAINED MLPs
Corollary B.3 (Distortion and Violation of Unconstrained MLPs). Let (fr)n be arbitrary sequence of desired violation values. There is an infinite collection of quasimetric spaces ((Y,, dn))m=1,2... with |x, n, Xn IR" such that MLP trained with squared loss in NTK regime converges to a function d that either
fails non non-tegativi,y, or
vio(d) 2 fn.
with probability 1/2 - o(1) over the random training set S' size m, as long as does not contain almost all pairs m/n" w(n 1133), and does not only include few pairs m/n? 2 w(n
Proof of Corollary B.3. This follows directly from Thm. 4.6 and standard NTK convergence results obtained from the kernel regression optimality and the positive-definitenss of the NTK. In particular, Proposition 2 of (Jacot et al., 2018) claims that the NTK is dositive-defintt when restricted to hypersphere. Since the construction in proof of Thm. 4.6 uses one-hot features, the input (concatena- tion of two features) lie on the hypersphere with radius 22. Hence, the NTK is guaranteed positive definite.
32

---

Published as a conference paper at ICLR 2022
10-8
Training MSE for ML Ps. trained on the left pattern
Training
right pattern
400
dy.
dy. zi for NiPS trained on the right pattern
patttern
300
200
2-
100
1-
200 400
200
1000
(a) Training losses for varying Note the scale of the vertical axis.
(b) Prediction on heldout pair d(y, 2) varying c.
Figure 7: Training unconstrained MLPs on the toy failure construction discussed in Sec. 4.2 (re- produced as Fig. 6). Two patterns in the construction have different constraints distance of the heldout pair (y, z). Plots show mean and standard deviations over 5 runs. Left:: All training conclude with small training error. Right: Trained MLPs predict identically for both patterns. Here standard deviation is small compared to mean and thus not very visible.
B.3.4 EMPIRICAL. VERIFICATION THE FAILURE CONSTRUCTION
We train unconstrained MIPs on the toy failure construction discussed Sec. 4.2 (reproduced as Fig. 6). The MLP uses 12-1024-1 architecture with ReLU activations, takes in the concatenated one-hot features, and directly outputs predicted distances. Varying с E {1, 10, 100, 1000}, we train the above MLP times on each of the two patterns in Fig. 6, by regressing towards the training distances via MSE loss.
In Fig. 7, we can see that all training runs conclude with small training error, and indeed the trained MLPs predict very similarly on the heldout pair, regardless whether it is trained on the left or right pattern Fig. 6, which restricts the heldout pair distance differently.
This verifies our theory (Thm. 4.6 and Corollary B.3) that algorithms equivariant to orthogonal transforms (including MLPs in NTK regime) cannot distinguish these two cases and thus must fail on one of them.
C PROOFS AND DISCUSSIONS FOR SEC. 5: POISSON QUASIMETRIC EMBEDDINGS (PQEs)
C.I NON-DIFFRENTIABIIITY OF CONTINUOCS- VALUED STOCHASTIC PROCESSES
In this section we formalize the argument presented in Sec. 5.3 to show why continuous-valued stochastic processes lead to con-differentiability. Fig. also provides graphical illustration of the general idea.
Proposition C.1 (Quasimetric Embeddings with Continuous- Valued Stochastic Processes are not Differentiable). Consider any I valued stochastic process { {R(w) such that & u' = P [R(u)= R(u')] < e for some universal constant < 1. Then IP [R(u) S R(u')] is not differen- tiable at any u d'
Proof of Proposition C.I. Assume that the quantity is differentiable. Then it must continuous in
and v.
We will use the (e, -ddefiiii of continuity.
At any Idd, consider small E (0, ) By continuity, since
PP (R(u)= < R(u) = P [R(u + 6) < R(u + 8)]
(142)
33

---

Published as a conference paper at ICLR 2022
R(v)
R(u +
RRW)
Rlu 61
Perturb
Perturb
R(V)
Alo)
R(U)
Atu)
Atut
R(u)
Atul
R(u) R(u
(10) Rio + 63) has bounded deasity on 3
F[R(w)
R(o]]
P( R(w)]
Moal probubilit atill R(x) Ris +
F(R(H) R(u++
(a) cantinuous-valuee stochastic process.
(b) Discrete-valued stochastic process.
Figure 8: Bivariate distributions from different stochastic processes. Left: In continuous- process (where (Na, NNr)) ) has bounded density if 0 * 0¹), perturbing one 0 + 0+ leaves
P [N = No+el = 0. Then one of PP [NN I Note] and P[No+e Σ No must be far away from 1 (as they sum to 1), breaking differentiability at either IP [Ng S Ng] = or P [Note I No+e] 1. Right: For cnscrete-valueee processes, most probability can still be left on No Note and thus do not break differentiability.
we can find E Rd such that
P (R((U)= & R(u + 6)] 2 1 [R(uu 5) S R(u)] 6.
(143)
(144)
However, by assumption, IP [R((w) R( + +)] <. Therefore,
P RR(u= v R(u+ + 6)] 2 - P [R u + 5) < R(u)) 2 -
(145)
(146)
which implies
2
P (R(u) < R(u
8) < R(u) 2 2- 2e c>
c 1.
(147)
By contradiction, the quantity must not be differentiable at any u = u'.
C.2 PQE-GG: GAUSSIAN-BASED MEASURE AND GAUSSIAN SHAPES
In Sec. 5.1, we presented the following PQE-LH formulation for Lebesgue measures and half-lines: PQE-LH (u, v)
Σ 0s -eeeep Σ (us.s v(z))))
(10)
Here, May and Unj receive gradient when Us.j S Vz.j-
Gaussian shapes parametrization. We therefore consider a set parametrization where no one set is entirely contained in a different set- the regions regions C. IR² between an axis and a ID Gaussian That is, for each given u E Rt we consider sets
density function of fixed variance o2 Saaaa
AN(u) & ((a.b) b E [0, fx((;
(148)
where fwrb; μ, o²) denotes the density of ID Gaussian V(H,o") with mean P and variance o² evaluated at b. Since the Gaussian density function have unbounded support, these sets, which are translated versions of each other, never have one set fully contained in another. For latent u E Baxk reshaped as 2D, our set parametrizations are,
A AN(
i [h], E [A].
(149)
Gaussian-based measure. These subsets R22 always have Lebesgue measure 1, which would make PQE symmetrical (if used with (scaled) Lebesgue measure). Thus, we use an alternative I² measure given by the product of R Lebesgue measure on the b-dimension (i.e., dimension of the function value of the Gaussian density) and R Gaussian measure on the a-dimension (i.e., dimension on the input of the Gaussian density) centered at with learnable variances (oeessure)) To avoid being constrained by the bounded total measure of also optimize learnale positive scales Crj > O. Hence, the each Poisson process has mean measure as the product of a R Lebesgue measure and R Gaussian with learnable standard deviation, then scaled with learnable scale.
34

---

Published as a conference paper at ICLR 2022
Note that the Gaussian measure should not be confused with the Gaussian shape. Their parameters also are fully independent with one another.
Computing measures of Gaussian shapes and their intersections. The intersection of two such Gaussian shapes formed by two Gaussian tail shapes, reflected around the middle point of the two Gaussian means (since they have the same standard deviation shape = 1). Hence, it is sufficient to describe how to integrate a Gaussian density on a Gaussian measure over an interval. Applying this with different intervals would give the measure of the intersection, and the measures of the two Gaussian shapes. Omit indices i,j for clarity. Formally, we integrate the Gaussian density far(a; u, o shape? over the centered Gaussian measure with variance d measure: which has density Jar(a: (a; 0, 0 measure):
f / far(;; u, o af 0, me da,
(150)
which is also another Gaussian integral (e.g., considered as integrating the product measure along the + u). After standard algebraic manipulations (omitted here), we obtain
a line of the form
f fN((; u, u haaeee) (a; O, o da
(151)
c exp (-u² /otto))))))
/ fN u o measure
Shape measure
2
da,
(152)
V2TTO total
rotal
total
for
total
shape + o measure
(153)
This can be easily evaluated using statistical computing packages that supports computing the error function and/or Gaussian CDF. Moreover, this final form is also readily differentiable with standard gradient formulas. To summarize,
each set A(u) has total measure
exp (-u² / /o (otal))
(154)
2T total
2
the intersection of A(v) and A(u2), for U2 has measure
c exp
(-22/ Potal)
measure 2
2
T shape measure
0²
SN
a; 112
da
(155)
V /2TO
o² total
total
+ c. exp
(-u2/ 1-22/ofool Totall
toc
fN
a; U
measure
shape measure
da.
(156)
/ 22To
utuz
total
0²
total
Interpretation and representing any total order. Consider two Gaussian shapes A(v) and A(w2). Note that the Gaussian-based measure (AGaussian is symmetric around and centered at O. Therefore,
|o| < [w2] |Gauussian ( (A(z)) > /GGaussian (A(uz))
(157)
JAGaussian ( (A(w) \ A(ua)) > (GGaussian (Al (u2) \ A(w)).
(158)
Moreover, scaling the rates of a Poisson makes it more concentrated (as a Poisson's mean grows the square of its standard deviation)
1 < <pa for Ji * 122 Then any total order can be represented as the limit of a Poisson process with Gaussian shapes, with the shapes' having their means arranged according the total order, the scale on the Gaussian-basee measure grows to infinity.
that lim P |Pois(CHL) < Pois(cu2))
C.3 THEORETICAL GUARANTEES FOR PQES
Theorem 5.2 (Distortion and violation of PQEs). Under the assumptions of Sec. any quasimetric space with size and treewidth admits a PQE-LH and a PQE-GG with distortion Ott log" n) and violation 1, with an expressive encoder (e.g.. a ReLU network with 2 layers and polynomial width).
In Sec. 5.4, presented the above theoretical distortion and violation guarantees for PQE-LH and PQE-GG. Furthermore, we commented that the same guarantees apply to more generally to PQEs satisfying mild condition. Here, first precisely describe this condition, show that PQE-LH and
35

---

Published as a conference paper at ICLR 2022
PQE-GG do satisfy it, state and prove the general result, and then show the above straightffrward corollary.
C.3.1
THE CONCENTRATION PROPERTY
Recall that PQES are generally defined with measures μ and parametrizations d (u, u A, &
Σ az E m (p..A) (p..A.) [ v)],
(13)
where
E
R (H.A) (T w:]] (IN)((A)( EN((A,())).
(12)
Because the measures y and set parametrizations themselves may have parameters (e.g., as in PQE-GG), consider them classes of PQEs. E.g., PQE-GG is class of PQEs such that the is the specific marssiann-bseed form, and is the specific Guassian-shape.
Definition C.2 (Concetration Property of PQEs). Consider a PQE class with h mixtures of quasi- partition distributions, each from k Poisson processes. We say that it has concentration property if satisfies the following. Consider any finite subset of X' C A, and arbitrary function g: X' - h There exists sequence of ((f(m, (((),, A(m)), such that
f(n); X" R4,
(m),4(" are valid members of this PQE,
E - (.) [ (f((() ( (v))) uniformly converges to - II 1 ,,()),, over all mixtures i and pairs x, E X".
sufficient condition.
It suffices make the probabilities (r,y, + P (A) s N,(A,(0)),
(159)
along some PQE sequence uniformly converge to the indicators
(x, y, i, + 1 {go("),)
(160)
This is sufficient since product of bounded functions is uniformly convergent, if each function is. Both statements below together form a sufficient condition for Eq. (159) to uniformly converge to Eq. (160):
1. For any g. there exists a specific PQE of this class satisfying Measures (of set differences) consistent with with some margin
0: Vi
[M], E [k], E X', X", g(x),,) < g(u)ss = (A,(A))((())) (a, ( Ai)(f())))
g(z),,) = g(y).s = (A.(A.)((z)))
=.,(A) (., =
Either of the following:
One side must be zero: Vi E [1],j J 1
(A))(())())) \ (cg((())))) (Hi (A))((()))) Ar,e)())))) =0, (161)
Max measure is bounded by some constant c 0:
max (A,, (f(x)) \ (,,((())) Se. s.y.i.3
(162)
2. For any given specific PQE of this class, for any positive scale d > 0, there is another PQE (with same formulation) whose measures (of set differences) equal exactly those of the given PQE scaled by d.
We now show that this is sufficient condition. Note that Poisson distribution has standard deviation equal to square root of its mean. This means that as we scale the rate of a Poisson, it becomes more concentrated. Applying to Poisson race probability, have, for 0 < ln e < P2,
36

---

Published as a conference paper at ICLR 2022
direction of Poisson race probability:
P [oiss (d 41)= I Pois(d u2)]
(163)
2 P [oois(d d (22 - Pois(d (d mi) ) d(p2 m1)1 s d(p2 - -m))
(164)
M1 u22
(165)
d(uz p1)
(166)
if H2 < c;
de
the other direction of Poisson race probability:
P [Pois(d p2) S Pois(d 11)
(167)
P [[Pois(d (d u2) - Pois(d mi) d(u2 m1)l 2 d(u2 m1)]
(168)
M1 + 12
(169)
d( M1)
2 if μn =0
de
(170)
2c if #/2 C.
de
Therefore, applying scaled versions of the PQE from Item above, we have thus obtained the desired sequence, where Eq. (159) uniformly converges to Eq. (160) with rate (1/dd).
Lemma C.3. PQE-LH and PQE-GG both have the concentration property.
Proof of Lemma C.3. We show that both classes satisfy the above sufficient condition.
PQE-LH: Lebesgue measure À and half-lines.
WL.OG, since X' countable, we assume that g satisfies g(z).. + g(y).. = !g(#){5 - g(y).sl > 1,
Vi [M].] E [k], E X' X
(171)
The encoder in Item above f: X' - Ax can simply be g. We then have (f)) This ensures that side is always the encoder f. Hence, PQE-LH satisfies this constraint.
Leb((- (wo)) = (g(v)s, -())(;)) (172)
Furthermore, scaling can be done by simply scaling
PQE-GG: Gaussian-based measure and Gaussian shapes (see Appendix C.2).
Because X' finit, can have positive constant margin for the PQE requirements in Item 1. (Infinite X' does not work because the total measure is finite (for specific PQE-GG with specific values of the scaling).) Concretely, we satisfy both requirements via
in descending order of g(-) we assign Gaussian shapes increasingly further from the origin;
scaling comes from that we allow scaling the Gaussian- measure.
Hence, PQE-GG satisfies this constraint for finite X.
C.3.2 GENERAL STATEMENT
We now state the general theorem for PQEs with the above concentration property. Theorem C.4 (Distortion and violation of PQFs (General)). Consider any PQE class with the concentration property. Under the assumptions of Sec. 4, any quasimetric space with size n and treewidth admits such PQE with distortion Ott log n) and violation 1, with an expressive encoder (e.g., a ReLU network with 2 hidden layers, (nn) hidden width, and (nn²) quasipartition distributions, each with (n) Poisson processes.).
Before proving this more general theorem, let us extend a result from Mémoli et al. (2018).
Lemma C.5 (Quasimetric Embeddings with Low Distortion; Adapted from Corollary in Mémoli et al. (2018)). Let M = (X, d) be a quasipseudometric space with treewidth f, and n = [X]. Then M admits an embedding into convex combination (i.e., scaled mixture) of (n²) quasipartitions with distortion O Ool'"g)n)
37

---

Published as a conference paper at ICLR 2022
Proof of Lemma C.5. The distortion bound is proved in Corollary 2 in (Mémoli et al., 2018), which states that any quasipseudometric space with n elements and t treewidth admits an embedding into a convex combination of quasipartitions with distortion Otllog") n).
To see that n²² quasipartitions suffice, we scrutinize their construction of quasipartitions in Algorithm 2 of (Mémoli et al., 2018), reproduced below as Algorithm 1.
Algorithm Random quasipartition of a bounded treewidth graph. Algorithm 2 of (Mémoli et al., 2018).
Input: A digraph G of treewidth hierarchical tree of separators of G' (H. with width I, and >> 0. Output: A random r-bounded quasipartition R.
Initialization: Set G G. H" H and R = EG). Perform the following recursive algorithm G*
and H"
Step 1. Pick z E [0, r/) uniformly at random.
Step 2. If (V(G))) S 1,terminate the current recursive call. Otherwise pick the set of vertices K = G*, Let Ha...., Hm. be the sub-trees of H* below root(H") H*) that are hierarchical trees of separators of C1,..., Cm respectively.
Step 3. For all (u. v) E EEG") remove (u, v) from R if one the following holds:
(a) da(u, u²) > and da (o, x)) S z for some vertex x E
for some vertex E K. Step 4. For all E fl,..., m) perform recursive call of Steps 2-4 setting G = (C, and H' H.
(h) dz( v) > and de (xr
Step 5. Once branches of the recursive terminate, enforce transitivity on For all u, v, w E V(G)
(u, v) E and (u, w) R, add (u, w) to R.
Many concepts used Algorithm are not relevant for our purpose (e.g., r-bounded quasipartition). Importantly, we observe that for a given quasimetric space, the produced quasipartition entirely determined by the random choice of z in Step I, which is only used to compare with distance values between node pairs. Note that there are n² node pairs, whose minimum distance is exactly (i.e.. distance from node to itself). Since 2 2 0, there are at most n² choices of that lead to at most n different quasipartitions, for all possible values of
The construction used to prove Corollary 2 of (Mémoli et al., 2018) uses exactly quasipartitions given by this algorithm. Therefore, the lemma is proved.
Lemma C.5 essentially proves the first half of Thm. C.4. Before proving the full Thm. C.4, restate the following result from (Hiraguchi, 1951), which gives us a bound on how many total orders are needed represent a general partial order (i.e., quasipartition..
Theorem C.6 (Hiraguchi's Theorem (Hiraguchi, 1951; Bogart, 1973)), Let (X, P) be partially ordered set such that X 2 4. Then there exists mapping f: X - RXX122] such that Vz, y X, xPy f(x) < f(y) coordinate-wise
(173)
Proof of Thm. C.4. It immediately follows from Lemma C.5 and Thm. C.6 that any quasimetric space with elements and treewidth i admits an embedding with distortion Olt log n) into a convex combination of n² quasipartitions, each represented with an intersection of O(n) total orders.
Because the PQE class has concentration property, for any finite quasimetric space, we can simply select a PQE that is close enough to the desired convex combination of n² quasipartitions, to obtain distortion Ott log" n). Since each Poisson process in PQE takes constant number of latent dimensions, we can have such PQE with (n dii""==diinsooonl latents and n² quasipartition distributions.
It remains only to prove that we can compute such required latents using the described architecture.
Consider any x X C Rdd Since X' is finite, we can always find direction ur E Rdd such that Ug. That is, x has a unique projection onto Ug. Therefore, we can have
Vy E X {0).00 uy + x TTuz.
c, b,, b_ E such that
c c.u + by =
(174)
-c u x: + b_ 1,
(175)
38

---

Published as a conference paper at ICLR 2022
but for y X {2), we have, for some > 0, either
c. c-u 1 + b+ = -1
(176)
u y + bb =a =a+2 2,
(177)
c. u y + b+ a
(178)
- u + b_ = -a.
(179)
Then, consider computing two of the first layer features as, on input 2,
[eeLU(c- u + b+) ReLU(-c- u b_)l.
(180)
which, if = = x, is [1, 1]: if o x, is either [0, 2 + al or [2 + a, 0j, for some a >
Then, one of the second layer features may sum these two features and threshold it properly would single out æ, i.e., activate only when input is x.
After doing this for all x E X' we obtain an n-dimensional second layer feature space that is just one-hot features.
The third layer can then just be simple embedding look up, able to represent any embedding, including the one allowing PQE to have distortion O log ri), as described above.
Because quasimetric embeddings naturally have violation 1, this concludes the proof.
C.3.3 PROOF OF THM. 5.2: DISTORTION AND VIOLATION OF PQES
Proof of Thm. 5.2. Lemma C.3 and Thm. C.4 imply the result. To see that polynomial width is sufficient, note that the hidden width are polynomial by Thm. C.4, and that the embedding dimensions needed represent each of the (n²)) Poisson processes is constant 1 in both PQE-LH and PQE-GG. Hence the latent space is also polynomial. This concludes the result.
C.3.4 DISCUSSIONS
Dependency log log dependency frequently occurs in distortion results. Perhaps the most well-known ones are Bourgain's Embedding Theorem (Bourgain, 1985) and the Johnson- Lindenstrauss Lemma (Johnson & Lindenstrauss, 1984), which concern metric embeddings into Euclidean spaces.
Dependency on treewidth t. Treewidth here works as a complexity measure the quasimetric. We will use simple example to illustrate why low-treewidth is easy. Consider the extreme case where the quasimetric the shortest-path distance on a tree, whose each edge converted into two opposing directed ones and assigned arbitrary non-negative weights. Such quasimetric space has treewidth 1 (see Defn. 2.2). On a tree,
1. the shortest path between two points is fixed, regardless of the weights assigned, 2. for each internal node u and one of its child c, the followings quasipartitions:
d/1 (2, y) A shortest path from to y passes (a, e)
d' (z. y) A 1.hortest path from to y passes (c, u)*
Hence it can be exactly represented as a convex combination of quasipartitions. However, both of observations becomes false when the graph structure becomes more complex (higher treewidth) and the shortest paths can are less well represented as tree paths of the tree composition.
Comparison with unconstrained MLPs. Thm. C.4 requires a poly-width encoder to achieve low distortion. This is comparable with deep unconstrained MLPs trained in NTK regime, which can reach 0 training error (distortion 1 on training set) in the limit but also requires polynomial width (Arora et al., 2019).
Quasipseudometriess and infinite distances. Thm. C.4 relies assumptions that (X, d) is not a quasipseudometric space and has all finite distances. In fact, if we allow a PQE to have infinite convex combination weights, it can readily represent quasipseudometric spaces with infinite distances.
39

---

Published as a conference paper at ICLR 2022
Additionally, PQE can still well approximate the quasimetric space with infinities replaced with any sufficiently large finite value (c.g., larger than the maximum finite distance). Thus, this limit is generally not important in practice (e.g., learning 7-discounted distances), where a large value and infinity are usually not treated much differently.
Optimizing quasimetric embeddings. From Thm. C.4, we know that optimizing PQEs over the training set S w.r.t distortion achieves low distortion (and optimal violation by definition). While directly optimizing distortion (or eπror on log distance or distance ratios, equivalently) seems a valid choice, such objectives do not always train stably in practice, with possible infinities and zeros. Often more stable losses are used, such as MSE over raw distances or 7-discounted distances 7", for Y (0, 1). These objectives do not directly relate to distortion, except for some elementary loose bounds. To better theoretically characterize their behavior, an alternative approach with an average-case analysis might be necessary.
C.4 IMPLEMENTATION OF POISSON QUASIMETRIC EMBEDDINGS (PQES)
Sec. 5.2 mentioned a couple implementation techniques for PQEs. In this section, we present them in full details.
C.4.1 NORMALIZED MEASURES
Consider PQE whose each of j expected quasipartitions is defined via A Poisson processes, with set parametrizations u + (u), i [h], E [k]. To robust to the choice of k; we instead use the normalized set parametrizations Al.j;
(u) a Aiz(u)/k;
[M] [k:)
(181)
This does not change the PQE's concentration property (Defn. C.2) or its theoretical guarantees (e.g.. Thms. 5.2 and C.4).
C.4.2 OUTPUTTING 7 DDISCOUNTED DISTANCES
Recall the PQE quasimetric formulation in Eq. (13), for a; 2 and encoder f: X Rdd
d(æz v) Σ 1 II PP [ooss(t.,(A,, \ (f,(f()))) <
Ats((())))
(13)
With discount factor 7 E (0, 1), we can write the ddiicounted PQE distance as
Ma..) = III 7
(182)
scalar that take value any (0,
Therefore, instead of learning as E [0), can learn bases B (0. such and define the r-discounted PQE distance as
(183)
These bases 3 (0, 1) can be parametrized via a sigmoid transform. Consider quasimetric learning w.r.t. errors 7-discounted distances (c.g., MSE). Unlike the parametrization with directly learning the convex combination weights a;'s such parametrization (that learns the bases 3 does not explicitly include and thus can potentially be more stable for wider range of choices.
Initialization. Consider learning bases 3, 's via sigmoid transform: learning by and defining 3 (bb)). We must take care in initializing these b, 's so that ar (b:)'ss are not too close to 0 or 1, since we take a product of powers with these bases. To be robust different numbers of quasipartition distributions, we initialize the each b, to be from the uniform distribution
U (0.52/h), -00.5- (0.752/h)).
(184)
40

---

Published as a conference paper at ICLR 2022
which means that, at initialization,
II
005 II (b.)) 0.5 E |0.5, 0.75].
(185)
RETA]
SE[A]
providing good range of initial outputs, assuming that the exponents (expected outputs of quasipar- tition distributions) are close to 0.5. Altematively, b, maybe parametrized by deep linear network, similar initialization is employed. See Appendix C.4.3 below for details.
C.4.3 LEARNING LINEAR/CONVEX COMBINATIONS WITH DEEP LINEAR NETWORKS
Deep linear networks have the expressive power regular linear models, but enjoy many empirical and theoretical benefits in optimization (Saxe et al., 2013; Pennington et al., 2018; Huh et al., 2021). Specifically, instead of directly learning matrix R=*" a deep linear network (with bias) of / layers learns sequence of matrices
M1 E IR'
(186)
M2 E IR m
(187)
(188)
Mi-1 E R RR-1-1X91--
(189)
M E R
(190)
B R
(191)
where the linear matrix can be obtained with
Mi M M2 M1 + B,
(192)
and we require
mmn, m2....,mm mm-1) 2 min(m, n).
(193)
In our case, the convex combination weights for the quasipartition distributions often need to be large, in order to represent large quasimetric distances; Poisson process mean measures with learnable
scales (c.g., the coussian-basee measure described in Appendix C.2), the scales may also need to be large to approximate particular quasipartitions (see Appendix C.3.1).
Therefore, we choose to use deep linear networks to optimize these parameters. In particular,
For the convex combination weights for h quasipartition distributions,
When learning the convex combination weights {a:)xE(M) parametrize a matrix E Rixh (i.e., linear map from Re to R), which is then viewed as a vector E A and applied an element-wise square transform + a² to obtain non-negative weights a E [0, ):
deep linear network to
When learning the bases for discounted quasimetric distances 3 's (see Appendix C.4.2), we use a deep linear network to parametrize matrix E | which is then viewed as vector I and applied an element-wise sigmoid transform - a{a) to obtain bases 3 E (0, 1)^
Note that here we parametrize matrix E R rather than 1 as above for ag's. The reason for this choice entirely specific to the initialization scheme we use (i.e., (fully- connected layer weight matrix initialization, discussed below). Here the interpretation a linear map is no longer true. If we use IR 1x,,, the initialization method would lead to the entries distributed with variance x
1/n,, which only makes sense if they are then added together. Therefore, we use R hx which would lead to constant variance.
For scales of the Poisson process mean measure, such PQE-GG, we consider a slightly different strategy.
Consider PQE formulation with h x k independent Poisson processes, from which we form h guasipartition distributions, each from & total orders parametrized by & Poisson processes. The Poisson processes are defined on sets
(194)
use mean measures
(195)
41

---

Published as a conference paper at ICLR 2022
and set parametrizations
{u + ALs(w))
(196)
compute quantities
Pi. (A) Ao)(1))
E for u CEERRR [h].j E [k].
(197)
Scaling each mean measure independently. Essentially, adding learnable scales (of mean
measures) w [0, )o)/ (or, equivalently, {wa. E [0, ki,) gives a scaled set of measures {wis M4. (e)))e())
(198)
This means that the quantities in Eq. (197) becomes respectively scaled as for urru R R i [h]. E [k].
Wajj Pa (As.s j (u) \ (1)(())
(199)
Convex combinations of all measures. However, we can be more flexible here, and allow not just scaling each measure independently. but also convex combinations of all measures. Instead of having as a collection of h k scalar numbers [0, o)), have a collection of (h x k)
vectors each having length (h x k) (or h x k-shape tensors)
{ws,J E )o)x*>>)>>> [E(()))E[[))
(200)
and have the quantities in Eq. (197) respectively scaled and combined as
Σ
Eiiss' pe. (Ai', J'() (v)) for u E RR. RR R E [M.. E [M] (201)
V'd'
Note that these still are valid Poisson processes for a PQE. Specifically. the new Poisson processes now all use the same set parametrization (as the collection of original ones), with different measures (as different weighted combinations of the original measures). This generalizes the case where each mean measure is scaled independently (as w can be diagonal).
Therefore, we will apply this more general strategy using convex combinations of all measures. Similarly to learning the convex combination weights of quasipartition distributions, we collapse a deep linear network into tensor E |xxxxxx and apply dlement-wise square + a², result of which is used as the convex combination weights w to ensure non-negativity.
Initialization.
For initializing the matrices (M1, M2...., Mi) of a deep linear network (Eq. (190)), we use the standard weight matrix initialization of fully-connected layers in PyTorch (Paszke et al., 2019). The bias matrix B (Eq. (191)) is initialized to all zeros.
When used for learning the bases for discounted quasimetric distances 3,'s 's (as described in Ap- pendix C.4.2), we have deep linear network parametrizing a matrix E 1 initialized in the same way as above (including initializing as all zeros). Consider the matrix up to before the last one:
(202) M is essentially a projection be applied on each row of the last matrix Mt Rhxm--1 obtain b, (which is then used to obtain bases Bg a a(b))). Therefore, we simply rescale the M subspace for each row of Mj and keep the orthogonal space intact, such that the projections would be distributed according to the distribution specified in Eq. (184):
M a M M2 M1 1
U1 u (0.52/"), a (0.75//')),
(184)
which has good initial value properties, as shown in Appendix C.4.2.
C.4.4 CHOOSING h THE NUMBER OF QUASIPARTITION DISTRIBUTIONS AND l: THE NUMBER OF POISSON PROCESSES FOR EACH QUASIPARTITION DISTRIBUTION
A PQE (class) is defined with h x k independent Poisson processes with means {Mu)ieejb]je [k] along with h x l set parametrizations (At, he(M))iEE For & pairs of means and set parametrizations, we obtain a random quasipartition. mixture (convex combination) of the resulting h random quasipar- titions gives the quasimetric. The choices of μ. and A are flexible. In this work we explore PQE-LH and PQE-GG as two options, both using essentially the same measure and parametrization across all i (up to individual learnable scales). These two instantiations both perform well empirically. In this section we aim to provide some intuition on choosing these two hyperparameters h and k.
the Number of Quasipartition Distributions Theoretical result Thm. C.4 suggest thats, for a quasimetric space with elements, n² quasipartition distributions suffice leam low distortion
42

---

Published as a conference paper at ICLR 2022
Train
Test
2
0
29
0
a
Triangle inequality =
? S d(a, b) + d(b, c) = 31
? 2 d(a, b) d(c, = 28
The 3-element quasimetric space, and the training pairs. Training set contains all pairs except for (a, c). Arrows show quasimetric distances (rather than edge weights of some graph).
Figure 9:
embedding. Since this a worst-case result, the practical scenario may require much fewer quasipar- titions. For instance, Appendix C.3.4 shows that (nn) quasipartitions is sufficient for any quasimetric space with a tree structure. In our experiments, E [8, 128] quasipartition distributions are used.
the Number of Poisson Processes for Each Quasipartition Distribution (Random Partial Order) It is well-known that such intersection of sufficiently many total orders can represent any partial order (Trotter, 1995; Hiraguchi, 1951). This idea is equivalent with the dominance drawing dimension of directed graphs (Ortali & Tollis, 2019), which concerns an order embedding of the vertices to preserve the poset specified by the reachability relation. In this graph theoretical view, several results are known. (Felsner et al., 2010) prove that planar graphs have at most 8 dimension. (Ortali & Tollis, 2019) show that the dimension of any graph with n vertices is at most min(wp, "), where up the maximum size of of incomparable vertices. A simpler and more fundamental result can be traced to Hiraguchi from 1951:
Theorem C.6 (Hiraguchi's Theorem (Hiraguehi, 1951; Bogart, 1973)), Let (X, P) be partially ordered set such that [X] 2 4. Then there exists a mapping f: X + [X1/2] such that Vx, E X, xPy +
((x < f(y) coordinate-wise.
(173)
Thm. C.6 states that 2 dimensions generally suffice for any poset of size 2.
2 Poisson processes (giving 2 random total orders) In our formulation, this means that using 2 will be maximally expressive. In practice. this is likely unnecessary and sometimes impractical. In our experiments, we choose a small fixed number k 4.
a
D EXPERIMENT SETTINGS AND ADDITIONAL RESULTS
Computation power. All our experiments run on a single GPU and finish within 3 hours. GPUs used include NVIDIA 1080, NVIDIA 2080 Ti, NVIDIA 3080 Ti, NVIDIA Titan Xp, NVIDIA Titan RTX, and NVIDIA Titan V.
D.1 EXPERIMENTS FROM SEC. 3.2: A TOY EXAMPLE
In Sec. 3.2 and Fig. 2, we show experiment results on a simple 3-element quasimetric space.
Quasimetric space. The quasimetric space has elements with one-hot features R Thequasi- metric and training pairs are shown in Fig. 9.
Unconstrained network. The unconstrained network has architecture 6- 6-128-128-38 128-32-1, with ReLU
activations.
43

---

Published as a conference paper at ICLR 2022
Unconstrained Network
Unconstrained Network
Asym. Dot Product (Output Square Root Distance)
(Output Distance)
(Output Square Root Distance)
(Training ixse 0.02 20066)
(Training Euse =..00- 0.02)
(Training lyse = 0.00 0.00)
100
100
80
60
60
Valid Range
10
10
20
30
100
20
30
(a) Unconstrained network that di- rectly predicts distance.
(b) Unconstrained network that pre- dicts distance with square a - a² transform.
(c) Asymmetrical dot product that predicts distance with square a + transform.
1 Space Embedding (Training fusE 0.00)
Euclidean Space Embedding (Training êuse 0.00)
Poisson Quasimetric Embedding (Training fwse
80
60
60
60
Count
40
40
40
Valid Range
10
20
30
10
20
30
0
10
20
30
(d) Metric embedding into & (c) Metric embedding into Eu- space.
(f) Poisson Quasimetric Embedding specified in Appendix D.1.
clidcan space.
Figure 10: Training different formulations to fit training pairs distances via MSE, and using them to predict on the test pair. Plots show distribution of the prediction over 100 runs. Standard deviations of the training enror are shown.
Metric embedding. The embedding space is 32-dimensional, upon which corresponding metric is applied. The encoder network has architecture 6-
with ReLU activations.
Asymmetric dot products. The embedding space is 32-dimensional. The two inputs are encoded with different encoder of architecture 1-128-128-32 with ReLU activations. Then the dot product of the two 32 32-dimensional vector is taken, which parametrizes a distance estimate
Poisson Quasimetric Embeddings. The embedding space is 32-dimensional, which parametrizes quasimetric distributions, each from independent Poisson processes using (scaled) Lebesgue measure and half-lines. We use deep linear networks, described in Appendix C.4.3. A deep linear network (without bias) architecture 8-32-32-1 parametrizes the convex combination weights {a, (ies)))) Another deep linear network (without bias) of architecture 32-64-64-32 parametrizes convex combination weights of the mean measures d [0, )2 Note that these do not give many more effective parameters to PQES as they are equivalent with simple linear transforms.
Optimization. All models are trained w.r.t. MSE on distances with the Adam optimizer (Kingma & Ba, 2014) with learning rate 0.0003 for 1000 iterations (without mini-batching since the training set has size 8).
Additional results. Results with additional formulations (together with the ones presented Fig. 2) shown in Fig. 10.
44

---

Published as a conference paper at ICLR 2022
D.2 EXPERIMENTS FROM SEC. 6: EXPERIMENTS
Triangle inequality regularizer. For methods that do not inherently respect triangle inequalities (e.g., unconstrained networks and asymmetrical dot products), we explore training with a regularizer that encourages following these inequalities. By sampling random triplets uniformly the training set, the regularizer is formulated as,
Enyy, max 7 d(x.,)) - - )
(203)
where the 7-discounted terms and the squared form allows easier balancing with the training loss, which, across all experiments, are MSEs on some y-discounted distances.
PQE settings. Across all experiments of this section, when given an encoder architecture mapping input to an Id latent space, we construct PQEs according to the following general recipe, to obtain the two PQEs settings used across all experiments: PQE-LH (PQE with Lebesgue measure and half-lines, and PQE-GG (PQE with Gaussian-based measure and Gaussian shapes, see see Appendix C.2):
(Assuming d is multiple of 4.) We use h -= d/4 quasipartition distributions, each given by
k - 4 Poisson processes;
deep linear network (see Appendix C.4.3), is used for parametrizing the convex combination weights a E Rd/4 or the bases /3 E TR//11 (see Appendix C.4.2), we follow the initialization and parametrization described in Appendix C.4.3, with hidden sizes [Thiideen Rhidden: Thiddenn (i.e., 4 matrices/layerrs) where Thhidden max (6, 21+ [dx/(4/))]).
PQE-GG,
The learnable o the log variance, which is initialized as zeros.
oo)d (one for each Poisson Process) is achieved by optimizing
The Gaussian-basee measures need learnable scales. We use a deep linear network to parametrize the [0, oo) dodd weights for the convex combinations of measures, as described in Appendix C.4.3. Similarly, it has hidden sizes [hiddee Rhidden:; Rhidden (i.e., matrices/lay- flog,
ers), where Thhidden A max(64, 20ooog d
Note that the PQEs add only few extra effective parameters top of the encoder (d for PQE-LH, and d + d² for PQB-GG), as the deep linear networks do not add extra effective parameters.
Mixed space metric embedding settings. Across all experiments of this section, when given an encoder architecture mapping input to an Rd latent space, we construct the metric embedding into mixed space follows:
(Assuming d is multiple of 4.) We use (1) (d/2) dimessiinal Euclidean space (2) (d/4)- dimensional & space, and a (d/ dimm)mimmmesionall spherical distance space (without scale).
Additionally, we optimize three scalar values representing the log weights of the convex combi- nation to mix these spaces.
DeepNorm and WideNorm method overview and parameter count comparison with PQEs. Both DeepNorm and WideNorm parametrize asymmetrical norms. When used to approximate quasimetrics, they are applied as d(x,, y) & f'symNorm (fEme(x) - fEnc(y)), where fEnc the en- coder mapping from data space to an RRd latent space and fAsymNorm either the DeepNorm or the WideNorm predictor that latent space (Pitis et al., 2020).
DeepNorm is modification from Input Convex Neural Network (ICNN; Amos al. (2017)), with restricted weight matrices and activation functions for positive homogeneity (a requirement of asymmetrical norms), and additional concave function for expressivity.
For an input latent space of Rd. consider n-layer DeepNorm with width (i.e., ICNN output size) and the suggested intermediate MaxReLU activation and MaxMean final aggregation (see (Pitis et al., 2020) for details of these functions). This DeepNorm predictor fDee (on latent
45

---

Published as a conference paper at ICLR 2022
space) has
#parmaters of /DrepNorm
(d x w)
from input to layer
nn 1) X w
W matrices between neighhoring layer activations
+
12 X w
intermediatte Max activations
(4+ 5)
function (with components) parameters
final MaxMean aggregation
which is on the order of Onw max(d, w)). In the common case where the hidden size w is chosen be on the same magnitude as this becomes ((d?)).
WideNorm based on the observation that
x:
- I ReLU(x:: :: =
(204)
is an asymmetric norm when W is non- non-negative, where :: denotes vector concatenation. Wide- Norm then learns many such norms each with a different W matrix parameter, before (again) feeding the norm values into concave function and aggregating them together with MaxMean.
For an input latent space of Rd consider WideNorm with e such learned norms with W matrices of shape (2(2))> This WideNorm predictor fwideNorm (on latent space), has #parmaters of fWideNomm = e (2d X w)
W matrices
+
x (4+5)
concave function (with 5 components) parameters
final aggregation
which is on the order (cdw). In the common case where both the number of components c and the output size of each component (before applying the 12-norm) are chosen to be on the same magnitude as d, this becomes (dd)).
For both DeepNorm and WideNorm, their parameter counts are much larger than the number of effective parameters of PQEs (d for PQE-LH and d2 for PQE-GG). For 256-dimensional latent space, this difference can be on the order of 106 ~ 10".
DeepNorm and WideNorm settings. Across all experiments of this section, we evaluate Deep- Norm settings and WideNorm settings, derived from the experiment setting of the original paper (Pitis et al., 2020). For both DeepNorm and WideNorm, we use MaxReL.U activations, MaxMean aggregation, and concave function of components. For DeepNorm, we use 3-layer networks with 2 different hidden sizes; 48 and 128 for the 48-dimensional latent space in random directed graphs experiments, 512 and 128 for the 512-dimensional latent space the large-scale social graph experiments, 128 and 64 for the 128 128-dimensional latent space in offline Q-learning experiments. For WideNorm, we components of size 32 and experiment with different numbers of components: 32, 48, and 128.
Error range. Results are gathered across 5 random seeds, showing both averages and population standard deviations.
D.2.1 RANDOM DIRECTED GRAPHS QUASIMETRIC LEARNING
Graph generation. The random graph generation is controlled by three parameters d, Pun and Pai is the dimension of the vertex features. Pun specifies the fraction of pairs that should have least one (directed) edge between them. Pai specifies the fraction such pairs that should only have one (directed) edge between them. Therefore, if Pun 1, Pai O, have fully connected graph; if
46

---

Published as a conference paper at ICLR 2022
Pun = 0.5, Pai 1, we have graph where half of the vertex pairs have exactly one (directed) edge between them, and the other half are not connected. For completeness, the exact generation procedure for graph of vertices is the following:
1. randomly add Pun n undirected edges, each represented as two opposite directed edges;
2. optimize Rnxd vertex feature matrix using Adam (Kingma Ba, 2014) w.r.t. Calign (a 2) + 0.3 Luniform( 3) from (Wang & Isola, 2020), where each two node is considered positive pair if they are connected;
3. randomly initialize network f of architecture 444096409994099-46066 with tanh activa- tions;
4. for each connected vertex pair (u, v), obtain du _ f((eeaurre()) - ((feature(t)) and dy-ou -du
5. for each (u, v) such that -u is among the top 1 1-pai/ of such values (which is guaranteed include both directions of the same pair due symmetry of du-so), make v the only directed edge between u and v.
We experiment with three graphs of 300 vertices and 64-dimensional vertex features:
Fig. 11: graph generated with Pun = 0.15, Pai = 0.85;
Fig. 12: A sparser graph generated with Pun = 0.05, Pai 0.85;
Fig. 13: A sparse graph with block structure by
1. generating 10 small dense graphs of 30 vertices and 32-dimensional vertex features, using
Pun = 0.18,, Pai 0.15,
2. generating sparse 10-vertex "supergraph" with di-dmensional vertex features, using
Pun = 0.22, Pai 0.925,
3. for each supergraph vertex
(a) associating with different small graph,
(b) for all vertices of the small graph, concatenate the supergraph vertex's 's feature to the existing feature, forming (4-diienssional vertex features for the small graph vertices, (c) picking random representative vertex from the small graph,
4. connecting all 10 representative vertices in the same way as their respective supergraph vertices are connected in the supergraph.
Architecture. All encoder based methods (PQEs, metric embeddings, dot products) use 64-128- 128-128-48 128-48 network with ReLU activations, mapping 64- 64-dimensional inputs to 48-dimensional latent space. Unconstrained networks use similar 128- 128- 128- 128-48-1 network, mapping con- catenated the 128-dimensional input to a scalar output.
Data. For each graph, we solve the groundtruth distance matrix and obtain 3002 pairs, from which we randomly sample the training set, and use the rest the test set. We run on 5 training fractions evenly spaced on the logarithm scale, from 0.01 to 0.7.
Training. We use 2048 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov & Hutter, 2016) starting from 10 to 0 over 3000 epochs. All models are optimized w.r.t. MSE on the 7-discounted distances, with 7 0.9. When running with the triangle inequality regularizer, 683 R 2048/3 triplets are uniformly sampled at each iteration.
Full results and ablation studies. Figs. 11 to 13 show full results of all methods running on all three graphs. In Fig. 14, we perform ablation studies on the implementation techniques for PQEs mentioned in Appendix C.4: outputting discounted distance and deep linear networks. On the simple directed graphs such as the dense graph, the basic PQE-LH without theses techniques works really well, even surpassing the results with both techniques. However, on graphs with more complex structures (e.g., the sparse graph and the sparse graph with block structure), basic versions PQE- LH and PQE-GG starts to perform badly and show large variance, while the versions with both techniques stably trains to the best results. Therefore, for robustness, we use both techniques in other experiments.
47

---

Published as a conference paper at ICLR 2022
Croundrruth D Ditance Natrix
$2
10
10T
10
Desphomm
Desptiorm
Vtochem
Wicchorm
Widdiom
15
10-1
-10
Lacarstiane mez Nei ex3l
Uncanetraines let via Square)
(Quipoi Diasourted Delance
(Dusptt Eolancel
joutpe poecounte Dizancel
Seymc d
10
13
10-3
10-h
12-1
0.0
0.5
3.8
0.5
6.5
0.0
0.0
0.5
Uncamat aives Not nes, Bigg Weight 6.3
10ulsst Disuncs
Unarrzaaid (Duju, Dilenue
Uhcensitahed Net fine fng Wright an
Uncoretmines (ourpe ybieoartedd Debhane dineg seg Weight un
&ling deg Weight 6.3
Were Reg Wright ab3
Unconstrained
Metric Embodeing
Asym, Det Product
Huidout MSE
DwepNorm
6.0
0.5
0.6
0.5
0.0
05
0.0
0.5
Widelorrm
Leceneraises Ne (ourpst airea flg. Waight w1
joutret Diewnte
Weaanst aaant Ne: Squard naz Weggt m
Unceseraibed let Reg.
tougpui pElsourlad Delanse
aireq Wegtt =1
flpp. Weigt
20-4
0.0
01
0.2
0.3
0.4
0.0
0.5
2.5
0.0
03
0.0
0.5
Training Set Fraction
Unporis io noo Net ecz)
Ueconatraine Net su Squard)
Uncosemmieed let
t0ugpo Disorun fed Detance
(ourpst batamcel
(outue yoccuutee Dieancei
amo
10
10
10
10-
13
Nett: Didaree
Space Metric
Tuc ceat Netric Embrndinn
Mitre Emboliing
0.0
0.5
3.5
6.0
0.5
Acam Dot Product ecai
Acym Product via Squart)
foym
iroduct (Surpe Datanoei
Dot Prosuct joutpee Dolroutte Didancel
(0.gpu Disouuttal Detance
Sipmcel
10
10
12
12
13
10
10a4
12a4
12
0.0
0.5
Det Product
Asym Dot troduct nea. Neg. Megglt u0
Nouttut Disoncce
(Gupp: Delanne
Asym Dor Prosut
touput pissourted
(outpse Didancsl
Bince Reg. Weight 0.S.
&ince Rog Wojit w0.
&enss Roy wajit u0s
dince say Wajlr w0.3
10
10"4
13-2
13-1
10-1
12-1
0.0
0.5
2.5
0.5
0.2
0.5
0.0
05
0.
0.5
Asym Dut troduct orneg Reg Weight =1
10 Bidancs
Asym: Produci hes, Reg Ve ghe
Asym, Dot Prosuct nes. Rig. Weight =1
toutpul Bltesuurtd Delance
alreq Sep, Vie gh: =1
nes Reg. Weight =1
0.0
0.5
0.0
05
0.0
0.5
Atym Froduct (Ckrpue
Souttu Diszance
Arym Product Squard)
Anym, Dor Poouct (outoo Dizancet feg Weight
touppst Dilscourted Celance
aires Whight
Airea
Repp Weight
5.0
0.5
3.5
6.0
0.5
0.0
0.
Figure 11: A dense graph. Individual plots the right show standard deviations.
48

---

Published as a conference paper at ICLR 2022
Croundrruth Ditance Natrix
12
10
Desphomm
Desptiorm
Viochem
Wicchorm
Widdimm
25
atto
20
10
Lasarstto mez Nei mx3l
Unconetraines Vet via Squard)
(ouipui Discourted Delance
(Duspot Eatancel
joutpe pfeccunted Disancei
Saymic i
13-1
10-2-
10-2
12-1
12-2
6.0
0.5
9.8
0.5
6.5
0.0
0.0
0.5
Uearrsaaich (Duju Disenue Wees Reg Wright u.a
Uncoretmines (ourpu ybieoarteed Debhane dineg seg Weight un.
Uncumata aines Nut nes, Bing Weight 6.3
10ulsst Dislancs
Uhcensitahed Net fiiee fing Wright a0
dliing deg Weiggt 0.3
Unconstrained
Metric Embodeing
10-1
Asym, Det Product DuepNerm Widetiorm
Heldout MSE
6.0
0.5
0.0
0.5
6.5
0.0
05
0.0
0.5
Lnceneraises Ne (ourput airea flag. Whighi w1
joutrut Bienente
Weaanst shval Net Squard) biinzz
Unceseraibed let Rig.
touipui yElsouurted Delanse flop. Weigh
20-3
aireq Weight
w1
20-1
0.0
011
0.2
0.3
0.4
0.0
0.5
0.0
0.
0.0
0.5
Traihing Set Fraction
Unporit oa nol Net ecz)
Jecanatraine Net su Squard)
Uncsseimieed let
(0ugpoi Disorun fed Detance
(Ouspsl batameel
(outue Coccrutte Dieancei
amo
10
10-
10-2
Didaatee Hott:
Netric Embrniding
Midri Emboldingg
Metric Entistcing
0,0
0.5
0.5
Atam Dot Product ecai
Acym Product via Square)
foym
iroduct (Surpu Dalannei
Asym, Dot Product joutpee Dilrrutted Didancel
(0.gpu Disoruttal Detance
Sipmcil d.
1
12
10
121
12
0.0
0.5
Det Product
Asym Dot troduct noc. Neg. Wedglt u1.
Nouttut bisoance
(Duipi Delanis
Asym Dor Protuct
(ouqpu pissoutted
(Outpse Didancal
Bénce Reg. Weight 0.S
& sinco Rlg. Wojji w0.
&ines Ray wajji -05
dince tay Wajlr w0.3
10-1
10-2-
13-2
5.0
0.5
0.5
0.5
0.2
0.5
0.0
0.
0.0
05
Asym Dut troduct o lineg Reg. Weight 11
10 Blaannc
Asym. Produci hes, Reg, Ve ght
Asym, Dot Prosuct nes. Rig. Weight =1
(outpul Bltesuurtd Delance mes Reg. Weight =1
alreg Seg, Wie gh:
5.0
0.5
0.0
05
0.0
0.5
Acym Froduct
Souttut Drszance
Arym Product Squard) Weight
Arym, Dor Poouct fegg Weight
toutpst BElscourted Delance
(Curpue
(outoo Dizancet
Aires fing. Whight
Airen ghn
Reg. Weight
5.0
0.5
6.0
0.5
0.6
0.
Figure 12; A sparse graph. Individual plots on the right show standard deviations.
49

---

Published as a conference paper at ICLR 2022
Groundrruth Datance Natrix
10-3
10-3-
S
10
0.0
Desphomm dtt
Desptiorm
Vtochor
Wieehor
Widdim
13-1
10-1-
10-1
12-
13
13
12
10
12
12
05
Lizorsti mez Nel mX3l
Unnonetraines let via Squard)
Incoretmined let Delance va Saymi i
(Duspot Eolancel
jouppe plecousted Didancei
12*1
10a
10
10"
12"
12
0.0
0.5
0.6
0.5
6.5
0.0
05
0.0
0.5
Unarssaain Dilenue Wlee Reg Wright u.3
Uncoretmines (ourpn ybieoarted Derhace
Uicamat aines Nut nes, Ring Weight 6.3
10ulsst Dislancs
Uhcensitabedd Net finee fing Wright =03
dliing deg Weight 0.3
dineg seg Weight an.
13
10
10-1
12
13
Unconstrained Netwerk Metric Embodeing
20
Asym, Dot Product
12
10a2
10a
12-a
12
Heldout MSE
DuepNorm
6.0
0.5
0.0
0.5
6.5
0.0
05
0.0
0.5
Widelorm
Lncendraisee Ne (Oupput
joutrit Biewnne
Uevanst sinsstiiiellae Net Squard) benz
Unceseraibed let Rig.
toutpi yElsouurted Delance
airea flgg. Whighi w1
aireq Weight =1
fiep. Weigh =1
13*4
10-4-
10
18
12
13
10-3
10-1
12-3
13-3
10-4
0.0
0.1
0.2
0.3
0.6
0.5
0.6
0.0
0.5
0.5
0.0
03
0.0
0.5
Traiiing Set Fraction
Unoorit aetoraataaa noo Net ecz)
Jecanatraises Net su Squard)
Net
Uncsseimieed let (outue Doccustie Dieancei
10ugpui Divoout fed Dstance
(Ouspst batamcel
amo
Nuy.
10-1
10
10 3
10
12
Didastes Hett:
Space Netri:
Tud dest Netric Embrniiing
Midri tmboliingg
13
10
10
12
13-1
10-3
10-1
10-
0.0
0.5
5.5
6.5
6.0
0.5
Aoam Dot Product ecai
Kcym Dot Product via Squart)
foym Projuct
iroduct (Surpur Datanne)
Asym, Dot Product 1outpee Dilerutte Didancei
10.gp/ Disouutted Detance
vi Sipmcid i
12
0.0
0.5
0.0
0.0
0.5
Product 20uttut Disoance
Aaym, Det Product
Asym Dot troduct ric. Neg. Wesglt -1.
(Gupp: Celance
Asym Dor Protuct
touppt plssouuted
[Dutpse Didancal
Bince Reg. Weight 00.
Ainco Rog Wojli w0.
&imes Ray Wujji -05
ditse tay Wajli -0.3
10-1
10-1-
16-4
18-4
13
12-3
13-1
0.0
0.5
0.5
0.5
0.2
0.5
0.0
0.
0.0
0.
Asym Dut troduct 6 orneg Reg. Weightt #1
10utzet Biaannc
Asym. Produci d hes, Reg, Ve ght
Asym, Dot Prosuct nes. Reg. Weight =1
(outpul Bleesurttd Delance
be:
alreg Seg, Vie gh: #1
nin Reg. Weight =1
13-1
10-1-
1E-1
13-4
13
13
10
10th
12-9
13
5.0
0.5
0.5
0.0
05
0.0
0.5
Anym Dott Froduct (Durpus
Dot Souttu Drszance oull Airen ghn
Arym Product Squard) nes, Reg, Weight
Arym, Dor Ponut Dizancet jostur feg Weight
toutpsi FElscourted Delance
siyma
dires figg. Whight
Weight
13:4
1
1
12:4
1
13
10-3
15-3
15-3
13-3
5.0
0.5
6.5
6.0
0.5
0.0
0.5
Figure 13: A sparse graph with block structure. Individual plots the right show standard deviations.
50

---

Published as a conference paper at ICLR 2022
Ablatioo PQEILH Danse Graph
Ablation Study Derse Graph
PQE-LH
*w tn
POE-GG
PQF-L11
Bicoumeed Det:
POT-GS
Berounned Duet
Kxx 10
POE
Diecoumted Dist. Deep Lncar Net
4 50
POB 00
Decourted Dist
Doep Lincor Ne:
XX 10m
Geoundrrut
HoloOUE
Coundtruh
2 00
10-9
3.2
04
0.3
0.2 Training Fraction
04
6.4
Training Fraction
Ablation Study of FQE-LH the Sparse Graph
Ablation Study PQE-GG the Sparss Graph
PQE UH
PgE 66
PQE-IH
Dicounted Diet
POF -G
Dicourted Dist.
Hobout MIE
PHE-U
Disoounted Dist
Doop Linaa Not
PGE 0G
Diccurted Dut
DDopp Linear Nic
Groundiuth Distance Mat
Hebou
Groundinzh Dizaacee Hatri
0.2
8/6
Training Fraction
Training Fraction
Ablation Study of PQE-LH on the Sparse Graph with Block Structure
Ablation Study of FOE GG on the Sparse Graph with Block Structure
POE
PQE-U1
Dacounted Diet.
PQL GG
Dacourted Dect
POE
Dicounced
POE-G5 0G
Dicourted Linear
Hodbut
Gmundiuuhh Distance Martt
Ho
Grouddnes Datence Hatrs
02
Training Fraction
Traiiin Fraction
Figure 14: Ablation studies of PQE-LH and PQE-GG on three random graphs.
D.2.2 LARGE-SCALE SOCIAL GRAPHS QUASIMETRIC LEARNING
Data source. We choose the Berkeley-Stanford scale directed social graph, which consists of 230 pages as nodes, and 7, 7,600,595 hyperlinks as directed edges. Additionally, we also use the Youtube social network (Leskovec & Krevl, 2014; Mislove et al., 2007) undirected social graph, which consists of 1,134,890 users as nodes, and 2,987, 7,24 friendship relations as undirected edges. Both datasets are available from the SNAP website (Leskovec & Krevl, 2014) under the BSD license.
(Leskovec & Krevl, 2014) as the large-
Data processing. For each graph, we use node2vec to obtain 128-dimensional node features (Grover & Leskovec, 2016). Since the graph is large, to construct training and test sets. Specifically, we randomly choose 150 nodes, called landmarks, and compute the distances between these landmarks and all nodes. For directed graph, this means computing distances of both directions. From the obtained pairs and distances, we randomly sample 2,500,000 pairs to form the training set. Similarly, we form a test set of 150,000 from a disjoint set of 50 landmarks. For the undirected graph, we double the size of each set by reversing the pairs, since the distance symmetrical.
the landmark method (Rizi al., 2018)
Architecture. All encoder based methods (PQFs, metric embeddings, dot products) use 128- 1048-2048-2048-511 network with ReLU activations and Batch Normalization (loffe & Szegedy, 2015) after each activation, mapping 128-dimensional inputs to 512-dimensional latent space. Unconstrained networks use similar the 256-dimensional input to a scalar output.
network, mapping concatenated
Training. We use 1024 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov & Hutter, 2016) starting from 10 to 0 over 80 epochs. All models are optimized w.r.t. MSE the d-discounted distances, with y = 0.9. When running with the triangle inequality regularizer, 342 z 1024/3 triplets are uniformly sampled at each iteration.
51

---

Published as a conference paper at ICLR 2022
L1 Ener
Prediction when tree
Method Family
Fonnulation
"-discommed
when trce
distances (x:10-
d-<
PQF-LH
3,0427 0.1527
187663 +: 0.0550
69 09.9424 :t 0,4930
IQU
PQE-GG
3.9085 0.1225
1,8951
0.0366
101,8200 1. 10.3970
Ouip distance
d)s. [(x:3)
3,8862 000092
2,1151
0.0241
59,5243 0,3700
Unconstrained Nets
Ouiut distance exp(()
d.s.y) (xp(F(s.))
3.3541 0.1759
1,0000 10 2.0199
5.3583 x 1.0582 10*
(without Trisngle heqqulity
Ouput distace via squiing
di..a) (](s.a)))
4.5663
0.2294
3.3459 0.2494
66.2613
11,6061
Regularisrr)
Ouipi yydiscommed distance
T [(r.a)
NaN #: Nal
Nal NaN
Kali NaN
Ouiut discoumed distance via sigmold of)
Ar 2 o(f(x.a))
3.1823 1: 0.3133
DO A NoN
65,5630 A 0,4287
Ouiput distance
dr..y) f(r,3)
288188 0.0625
2:2109 +: 0.041
61,3209 :t 0. 3936
Unconstrained Nets
Ourpur distance via exp(:)
di..u) 2xp(f exp(f(r.u))
2.9344 0,0455
DO 1. NoN
00 1. NoN
(Tringll Inagiality
Ouipu distance via aquring a +
d [)(=
4.9947 0.4198
16,5445
20.5175
+ 6,4216
Regulazizer Weight 0.3)
Oulput y-discoumed distance
Ae f(r.a)
Nel
Outpur r-diccoumed distance agmood of
Ai 2 elfir.
2,9178 0.1351
1.
Oulpu distanes
dr..)) f(x.3)
3,0481 0.1272
2,5729
0.1378
60,4640 + 1890
Unconstrained Nets
Oupu distance via exp(:)
ds..y) 4 cxx(f(a..))
3/0161 0,0718
DO de NoN
3.1289 10 6.2579 x 10
(Tringge Iequulity
Ouspu distanee via squiing a
d...a a (f(s.a))
4,4921 0.3534
3,6930
0.4896
50,6206 +: 66.5704
Regulsrier Wright = 1)
Ouiput y-discommed distence
- [(+.a)
4.4046 0.5167
2.7873
0.0770
31,3195
Ouput discoumed distance sigmold of)
ar a(f(x.u))
2.9314 0.1022
2,2634
0.1147
DO 1.
Duipar distance
dr.y) t f(r,3)
0.5277
0.208
58,1193 0:4488
Uncomstrained
Ouipur distance via expl-)
drr.y) exp(F(r..)))
3:5713 0,2002
212,5421
114116.00 4256
(Trisngle Inoquality
Oulpa distance via squiing
dz. [11,,
4.3745 0.3709
2,0491 0.2228
53,1119 + 5,5442
Regularizer Weight
Ouspu y-discoumed distance
-- ((5.9)
7.3466 0.6486
3,5032
+ 0.152
76,9000 # 0.4697
Outptt y-discoumed distance via digmoid (()
Ar vll
3.5818 0.3665
00 1:
65.7209 1. 0.8646
Ouiput disiance
dx 1 [(x)"9ts) yls)
3.1622
Nool
23,4270
Asym Produces
Ouiuu distance exp(.)
ds..) cxp(
NoN NaN
NaN NON
NaN NaN
(withont Trisngle Inequlitt
Oupu
squiing
ds..) ((oc))
45.1056 000056
2.5195 10 2.151 10
2.6794 10" 2.539% 10"
Regulariser)
Ouiput discoumed distance
-- f(s) styl
NoN NoW
NaV NON
NaN NoN
Ouiic discoumed distance via sigmoid of
Ar o(f(s) (999))
48,1075 1 0.0112
DO LL NON
DO L. MoN
Output distsnce
di.. f(+) sta)
NoN Roh
New NAN
KAN St NaN
Asym. Dat Products
Outpu distance via expé:)
dis.g) exp(
NoN Now
NaV NoN
RaN NaM
(Triangle Inoquliit
Ouiput disiance via squring a -
dr..g) [[(=)] v(s))"
1041 + 0.0035
1.9498
10 7.9641
1.6099 10 3,7099
Regulatierr Weight 0.3)
Ouipe 7-discoumed distance
A [(+) sts)
Nel
Nah
NaMk
Ouput r-discoumed distance sigmoid
Ar e(r(s)Ta(v))
45,1108 D.0130
Ouipat distance
drr.y) f(x) pla)
NoN NoN
NaN NON
NaN NoN
Asym. Det Products
Ouipt distance via exp(.)
dss.y) cxp(((ss s(v))
NoN NaN
NaN NON
KaN NON
(Tringle Inoquality
Ouipu distance via squaing a -9 o²
dis.a) [(x0)"
45.1021 #: 000002
2,2986
10 4: 9.1970 x 10"
2,5000
10" 1.4464 x 10"
Regulariser Weight
Outpt y-discoumed distance
A--i f(r) stal
NoN NoN
NaV NoM
KaN NoM
Ociput discoumed distance sigmold of)
Ar (ooo))
58,4894 2322
Do L.
Do J.
Duipur
Me. Sh Taty)
NaW Nel
NoN
Asym. Products
Ouipu via exp(.)
dz.y) usp(F w(s))
NaN Nak
Nal NaN
KaN NaN
(Tringll Inoqualit
Ouiput distance via squiing
dz.,)) 4 "[it)
48.1031
0.0020
23522
10 6429 x 10
1,7025
10 1.17000 x 10
Regularierr Weight
Ouspu y-discoumed distance
Ar [(s]Tsts)
Nolk New
Nvel NNN
Kali NaN
Ouip y-discoumed distance via signoid ())
Ar (((e))
48,3034 + 0.4485
Do = NaN
oo d: Mak
Dochdean space
dr. 1f(e) flaill,
13,5952 1. 0.2667
7,5399 0.0422
53,8500 1. 3.84400
Mesie Enbhodiings
4 space
de 1/(a) flaill,
18,0521
1. 0.3546
7.1154
0.1835
66.2507
3.3308
Spherical space leamable caale
6.9545
0.0877
32,1458
0.4562
Mixing above spaces learnable weights
17,8312
7,3493
1016
51,7481
3.6444
DoepNoems
8daye: 128-wich
7.0862
0.3170
2.4498
0.8637
111.2200
2.5045
layer 312 wich
5,0715
0.1348
2,0853
0.0633
120.0452
4.3825
Roommenenn (each sine 32) 48 component reach of size 32)
3,5338
0.2120
1,7694
0.0233
126.6500
2.8678
WideNeems
5.6842
0.2365
1,8081
1: 0.0680
122,6833 1: 5,5005
125 component (exch of size 32)
3.8125 0.2331
1,8096
0.0765
1283427
5.1412
Table 2: Quasimetric learning on the large-scale directed Berkele-StanfordWeeGrra..
52

---

Published as a conference paper at ICLR 2022
MSE w.E. 7-ddiscoentted
Prodiction of when troe d
Method Family
Fommslation
when true
distances (x:10-1)
of < 0c
PQE-LH
2,4400 1: 0.0695
0,4800 +: 0.01
NaN NoN
PQEs
PQE-GG
2,5895 + 0.0318
0.6997 0.0042
NaN
Output distance
d(s.p) f(r.a))
1,4883 # 0.0168
0,5084 0.0029
NaN NoN
Unsomstrained Nets
Outpul distance via exp(.)
d(r.a) exp(f(r.g))
1,5223 1: 0.0160
0,1910 1 0.0151
NoN NaN
(withour Triangle Inequality
Output distance via squaring a
d(r.a) A (f(r,))))
2,2955 + 1.1674
0.6885 + 0.1409
NaN NaN
Regularizer)
Output y-diecounted distince
Seai ((a.))
1,5069 + 0.0028
04975 + 0.0211
NaN NaN
Output y discoonsted distance via sigmoid of))
(ra a (tf(s.)))
1,4802 +: 0.0197
0.5082 1: 0.0036
NoN NaN
Octput distance
d(s.a) A f(x.a)
1,5009 1: 0.0208
0,5107 1: 0.0032
NoN NaN
Uncomstrained Nets
Outpot distance via exp(-)
d(r.a) 4 exp(s(r.u))
1.5206 +: 0.4444
0.0098
(Triangle Incquality
Output distance squaring a
d(x.g) (f(a.)))?
1.7398 + 0.3896
0.5488 0.0600
NaN NoN
Regalatizer Weight 0.3)
Outpui 7-diiscuuied distance
* ((..v)
1,5005 1: 0.0148
0.4966 1 0.0121
NoN NoN
Output y-diecounted distance via sigmoid of)
Kna0 (()()))))
1,4811 +: 0.0108
0.5089 + 0.0026
NaN + NaN
Ourput distance
dts.a) A (().))
1,4999 + 0.0043
0,5107 + 0.0046
NaN NGN
Uncomstrained
Ourput distance via exp(()
d(s.a) A cxp(f(ss. o1)
1,5224 + 0.0376
0,4948 + 0.0169
NAN NGN
(Triangle Inequality
Octput distance via squaring
d(s.a) A (f(x.))))
1.8875 1 0.507s
0.5692 1 0,0683
NoN NaN
Regularizer Weight-
Output 7-discounted distance
(oww A f(a.9)
1,4769 + 0.176
0.01 28
Output disccoouttedd distance sigmoid of:)
14846 + 0.0115
0.5088 0.0021
NaN NaN
Output distance
d(s.a) ((x.))
1,4939 1: 0.0110
0.5099 :: 0.0018
NaN d: NaN
Uncomstrained Nets
Outpui distance via exp(.)
d(x.a) & exp()(an.)))
1,5154 1: 0.0389
0.4871 1 0.0174
NaN NoN
(Triongle Incquality
Ourput distance via squaring a
a²
d(s.a) a (f(r.))))
2,4747 + 1 1.8600
0,6505 + 0. 0.17
NaN NGN
Regolarizer Weight
Octpul 7-discounted distance
Arawi A f(a.v)
1,4915 1 0.0127
0.4963 1 0,0160
NaN NoN
Output y-discounted distance sigmold m{.)
Arxs) a ())
1,4299 0.0133
0.5084 0.0029
NaN
Output distance
d(x.a) f(x)) g(v)
2633.7907 1 NSN
11.3879 NoN
Asym. Dot Products
Output diszanoe via exp(.)
d(r.g) expC](6)) ((()))
NaN + NaN
MaN + NaN
NAN
(without Triangle Incqullit
Output distance via squaring a +
d(x.a) (f(=) ([())'s(0))*
339.1550 1: 0.0022
7,8948 x 10" 4 7,4010 x 10
NaN NaN
Regularizer)
Outpui y-discounted distance
* [(a)Tata)
2.6920 :: 1.2685
0,7062 :: 0.2156
NaN NaN
Output p-discounted distance via sigmoid of))
Aras 2 otf(s)) 9(a9)
182.2068 + 1.2382
de NAN
NaN NaN
Output distance
d(s.a) A f(x)) 9(s)
9,9748 10" + NaN
8.1867
NaN NoN
Asym. Products
Outpui distance exp(-)
d(x.a) A exp(r(a)) o(2))
NaN 1:
NoN
(Triangle Incquality
Ourput diszance via squaring a
d(s.g) (f(e))o(s))'
339.1560 + 0.0010
6.8658
+
10"
NaN NaN
Regulasizer Weight 0.3)
Output 7-discounted distance
Atwin [(x]T ptx)
NaN 1: NoN
NaNl 1: NoN
NaN NaN
Output y-diecounted distance via sigmoid e1-)
Araa o()()) 9(59)
183.3337 + 1 1.0384
n0 + NAN
NaN NaN
Output distance
d(x.g) à f(x) star)
NaN d: NoN
NaWV 1: NoN
NaN NoN
Asym. Dot Products
Output distance via exp(.)
d(r.a) A exp( (o(9)
NaN + NAN
NaV NAN
NaN NNN
(Triangle Incquality
Output distance via squaring a a²
d(s.g) A (f())'s(w0)"
339.1552 + 0.0021
7,4588 10 3.7277 10
NaN NoN
Regularizer Weight- 1)
Outpul 7-discounted distance
NuN
NoN
Ourput 7-discounted distance sigmoid at.)
Arai off o(a))
191,0928 + 9.7137
NaN NoN
Output distance
d(s.a) A f(o) sta)
NaN + NoN
NaVV +: NoN
NaN NaN
Asym. Det Products
Ouspui distance via exp(-)
d(x.g) è exp(f(x)) o(y)))
NaN 1: NaN
NaV 1: NoN
NaN NaN
(Triangle Inequality
Ourput distance via squaring a
a²
d(r.a) A (f(e) o(1))"
399.1556 + 0.0000
9,0283 x 10" + 6.0203 x 10"
NAN NGN
Regularizer Weight
Octput disccountedd distunce
Aeai & ((x]
NaN 1 NoN
NaV NoN
NaN NaN
Octput disccouunted distance via sigmoid of.))
(xx0) & o(f(x)) e(a))
228,0300 37 02.0632
NaN NoN
Eaclidean space
d(s.g) A If(x) fo0l
1,3131 4: 0.0671
4: 0.0128
f space
d(r.s) [f(r) rGll,
3,5993 +: 1.5986
0.7787 :: 0.1843
NoN NaN
Metric Emheddings
Spherical distance spuce w/ learaalee scale
d(x.a) A a arcoee (7 m
6.7731 1: 0.195
1.0829 :: 0.0177
NaN NaN
Mixing ahove chree spaces w/ learnable weights
2.1014 +: 0.0685
0.5923 +: 0.0109
NaN NaN
3-layer 128-width
8.1922 1 0.3476
1.1834 0.0213
DeepNocms
3-layer 512-width
5,4366 + 0.0855
0.9666 + 0.0072
NaN NaN
32 composent (each of size 32)
3.0841 # 0.0667
0.7272 + 0.0068
NaN NaN
WideNorms
48 component (each of size 32)
3,0438 1 0.132
0.7247 1 0.0173
NaN NaN
128-component (each of size 32)
2,9964 + 0.1363
0.7173 + 0.0166
NAN NSN
Table 3: Metric learning on the large-scale undirected Youtube graph. This graph does not have unreachable pairs so the last column is always NaN.
53

---

Published as a conference paper at ICLR 2022
Full results. directed Tables 2 and 3 show full results of distance learning these two graphs. On the PQE-LH performs the best (w...t discounted distance MSE). While PQE-GG has larger discounted distance MSE than some other baselines, it accurately predicts finite distances and outputs large values for unreachable pairs. On the undirected Youtube graph, perhaps expected, metric embedding methods have an upper hand, with the best performing method being an Euclidean space embedding. Notably, DeepNorms and WideNorms do much worse than PQES on this symmetric graph.
D.2.3 OFFLINE Q-LERNIIGG
As shown in Proposition A.4 and Remark A.5, we know that a quasimetric is formed with the optimal goal-reaching plan costs in MDP M (S, A. R, P, Y) where each action has unit cost (i.e., negated reward). The quasimetrie is defined X' _ S U (S x A).
Similarly, Tian et al. (2020) also make this observation and propose to optimize a distance function by Q-learning then used with standard planning algorithms such as the Cross Entropy Method (CEM) (De Boer al., 2005). The specific model they used is an unconstrained network J:: (s,a, as,aa,s)) 5') - R. outputting discounted distances (Q-values).
collected set of trajectories. The optimized distance function (i.e.. Q-function) is
Due to the existing quasimetric structure, we explore using PQEs as the distance function formulation. We mostly follow the algorithm in Tian et al. (2020) except for the following minor differences:
Tian et al. (2020) propose to sample half of the goal from future steps of the same trajectory, and half of the goal from similar states across the entire dataset, defined by a nearest neighbor search. For simplicity, in the latter case, we instead sample random state across the entire dataset.
In Tian et al. (2020), target goals are defined as single states, and the Q-learning formulation only uses quantities distances from aate-action pairs (s, a) E S x states s': d((s, a), s').
However, if we only train on d((ss, a), quasimetric embeddings might not learn much about the distance to state-action pairs, or from states, because it may simply only assign finite distances di(s, a), 8'), and set everything else infinite. To prevent such issues, we choose to use state-action pairs as target goals, by adding random action. Then, the embedding methods only need to embed state-action pairs.
In planning when the target is actually single goal s' E S, we use the following distance/Q- function
a( (()
Σ d((ss (s',
(205)
A
d'EA
Such a modification is used for all embedding methods (PQEs, metric embeddings, asymmetrical dot products). For unconstrained networks, we test both the original formulation (of using single state goals) and this modification.
The environment is grid-world with one-way doors, as shown in of Fig. 15, which is built upon sym-minigris (Chevalier-Bi -oiiverr et al., 2018) (a project under Apache 2.0 License). The agent has 4 actions corresponding to moving towards 4 directions. When it moves toward a direction that is blocked by wall or one- one-way door, it does not move. States are represented as 18-dimensional vectors, containing the 2D location of the agent (normalized to be within [-1, 1J9). The other dimensions are always constant in our enviroment as they refer information that not be changed in this particular environment (c.g., the state of the doors). The agent always starts at random location in the center room (c.g.. the initial position of the red triangle in Fig. 15). The environment also defines goal sampling distribution as a random location in one of the rooms on the left or right side. Note that this goal distribution only used for data collection and evaluation. In training. we train goal-conditional policies using the goal sampling mechanism adapted from Tian et al. (2020), as described above.
Environment.
Training trajectories. To collect the training trajectories, we use e-greedy planner with groundtruth distance toward the environment goal, with a large e = 0.6. Each trajectory is capped to have most 200 steps.
54

---

Published as a conference paper at ICLR 2022
1.0
0.8
P|success)
0.6
0.4
PQE
Unconstrained Network
Asym. Dot Product
0.2
Metric Embedding
DeepNorm
WideNorm
0.0
200
400
600
800
1000
Number of Training Trajectories
Figure 15: Grid-world offline Q-learning average planning success rates. Right shows the environ- ment.
Architecture. All encoder based methods (PQEs, metric embeddings, dot products) use 18-2048- (048-2048-1024 network with ReLU activations and Batch Normalization (loffe Szegedy, 2015) after each activation, mapping a 18-dimensional state to four 256-dimensional latent vectors, cor- responding to the embeddings for all four state-action pairs. Unconstrained networks use a similar architecture and take in concatenated 36-dimensional inputs. With the original formulation with states as goals, we use 36-2048- 118--2088-2200 1118-2048-2555 2-6-44 network to obtain RIAI output. representing the distance/Q-valuee from each state-action pair to the goal; with the modified formulation with state-action pairs as goals, use 36-2048-2044 201--220882222222 16 network to obtain a R R[A[X| output.
Training. We use 1024 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov Hutter, 2016) starting from 10-4 to ( over 1000 epochs. Since we are running Q Q-learning, all models are optimized w.r.t. MSE on the 7-discounted distances, with = 0.95. When running with the triangle inequality regularizer, 341 & 1024/3 /3 triplets are uniformly sampled at each iteration.
Planning details. To use the learned distance/Q-functi perform greedy 1-step planning, where always select the best action in A according the learned model, without any lookahead. In each of 50 runs, the planner is asked to reach goal given by the environment within 300 steps. The of 50 initial location and goal states entirely decided by the seed used, regardless of the model. We run each method 5 times using the same set of 5 seeds.
for planning towards given goal, we
Full results. Average results across 5 runs are shown Fig. 15, with full results (with standard deviations) shown in Fig. 16. Planning performance across the formulations vary lot, with PQEs and the Euclidean metric embedding being the best and most data-cfficient ones. Using either formulation (states vs. state-action pairs goals) does not seem to affect the performance of unconstrained networks. We note that the the asymmetrical dot product formulation outputting discounted distance similar to Universal Value Function Approximators (UVFA) formulation (Schaul et al., 2015); the unconstrained network outputting discounted distance with states as goals is the same formulation as the method from Tian al. (2020).
55

---

Published as a conference paper at ICLR 2022
LH
1.00
0.75
0.75
0.50
0:50
0.00
0.00
250
500
750
1900
250
500
750
1000
DeepKoem
Deeptorm
Wieakerm
Wideflarm
WideWerm
tsyer
(52
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.50
0.00
0.00
0.00
0.00
0.00
250
500
750
1300
250
500
750
1000
250
500
750
1000
250
500
75.
1003
250
500
750
1000
Uncomatreened Net
State Goek
State Gea's
State Cosls
Stare as Gools
State as Goals
(0utput Discouuted Distance
(Outou: Distande)
(Ouput stance exp)
D'stanic Square)
(Curptt Si Distnnce
Signold
1.00
1.00
0.75
0:75
0.75
0.75
0.75
9.50
0.25
0.25
0.25
0.25
0.25
0.00
0.00
0.50
0.00
750
1000
250
250
500
750
500
750
1000
250
Unconstraneed Met (0utput Disoounted Distance
Unconstraned Net (Qutour D-stanoe)
Unconstrainee Net Gosls (Ouque stance vi expi 6rneg Reg. Weight w03
Uncondtrainet Not
Unconemained (Curput Discountedd Distancee Rep. git w0.3
(Outout Datance via Square)
vo Simaald of Reg, Weight
Reg. Neight
noo. Reg.
0.75
0.75
0.75
0.75
0.75
0.50
0.25
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.50
0.00
750
1000
250
250
500
750
500
750
1000
250
1000
Rnconntrained Met State Seeb
Unconetree ned Net
Uncomdrrinne Met
Unvonddraised Net
Uncomersired
(Dutput Sosconttddd Distance
(Outou:D Distando)
(Ouquut o stanks via expl Aincs Rep. Welghtt
(Outaut Diaang via Squara)
(Ourput soocouuied stancel moo. Bag. Weight
vie Sigmai at A-inea, Rag. Weight
A/1e2 Nog. Welglt
A-moo. Rag. Weight
1.50
1.00
0.75
0.75
0.75
0.75
0.75
0.25
0.25
0.5
0.25
0.25
0.00
0.00
0.00
0.50
0.00
Uncongtranee Net State Scols
Unconstran nod Nct
Usconstro Not
Uscandrainned Net Store
Unavegzained het (Durut scDcuudd D Datanne)
(O.tpur p-Baconntedd Dicance
(Qutout D.stando)
(Qupple D staree va espi
(Outout stance via Squarc)
via Sigmari of
Oriees Seg. Weeghe
A4neg Reg. Weelght
(-nee Reg. We ght
S-nen Reg Welept
d4heeg Reg. Weight
3.00
1.00
1.00
1.50
1.00
0.75
0:75
0.75
0.75
0.75
0.25
0:25
025
0.25
0.5
0.00
0.00
0.50
6.00
1900
1900
Unconddrepee Ne:
Unconetnened Net Gools (Outou: (astno
Uscorstre ind Het (Quspie D stance via esp)
Unconatrained Nec (Outbut Distanic via Square)
Uncomezelteed hat (Durpit yO Dalance)
strtetctionn et Goak y-aconutted Dieance via Sigmal ot
1.00
1.00
1.00
3,00
1.00
9.50
0.50
0.50
0.50
0.50
0.25
0:25
0.25
0.25
0.00
0.50
0.00
250
750
1560
250
500
1000
250
500
750
1000
250
500
750
1009
250
500
1000
Figure 16: Grid-world offline Q-learning full results. Individual plots show standard deviations.
56

---

Published as a conference paper at ICLR 2022
Uncoratraied Stgie-Adion as Soas
Unconstra ned Stale Action as Gools
Unconstranee hot Aeceen Goals (Ourpot Distance b Ineg, Reg. Weight 0.3
Uncondtrafee Net State, Action as Goals drines Reg. Weight 0.3
Unconatea noe Not Stata-Action Goats soouneed &-ires Reg. Weight +.3
Skymo
6. neg Reg. Weight 0.3
brnen Reg, Weight 0.3
1.0
1.-
1.0
3.0
1.0
0.5
0-
0.5
0.5
0.0
0.0
unconstraned Net State Geas (Outait Diszaunted Dissance
Liveenstra med Net
inco hot State
Lncondd rained Ne:
Usconsto nod Net
Action jousout Dipaaoo))
Gyols (outout Pisanno, via Squard) A- neg Reg. Wi sit
(Ourpet Diedance vis Hop) binenn Reg Weight
(0 o0utpi ya scounted D didannel Aiiee Reg. Weight
via sigma d 10
/ehees Reg. Weight
Aetes Reg. Weight =1
1.0
3.0
0.5
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
250
500
730
1200
250
500
750
1000
250
520
750
1000
250
500
750
1200
250
502
750
1000
Unconstrolted Net (OUAAA y Diszounted Distance
Uncommttra ned Not
Unconnatraine redieet Net State (Dutaut nistance via Square)
Unconstro ned
Action joucout Dezanoo)
State Action 35 Gools
Stoto Action Geals
(Durpul Distance mxp)
(0 (0.tput yo scoumted Didennel
Sigma 1)
Weighe
Reg.
Weigst
0.5
0.5
0.0
0.0
250
500
750
1000
250
500
750
1000
250
5.0
750
1000
250
500
750
1009
250
500
750
1000
Euclidesn Merric Emaedting
f. Mepic Embudding
Metric Embedding
Mebiic Embeddinng
3.0.
1.0
1.0
3.0
0.5
0.5
0.5
0.0
0.0
Asym, Dut Product
Asym, Out Product
Acym, Dot Product
Asym, Dot Product
Asym, Out Product
(Outokk y Biscounted Distance
Square)
10 (0.tput Distanel
0.0
0.0
250
100
750
1000
250
500
1020
250
1030
250
500
750
1000
250
500
750
1000
Asym, Dok Product (Ourput Distance via exp)
Aaym Product
(OURDAR y Diisouunted Distance via Sigmo d Reg. Weight
10ulous Dasaans))
(Dutzui Datancee via Square)
(Output sounnted O Distancel
nco Weight
Reg. Weight
Srhee Rez. Weight -..
5ines Weight =0.3
0.5
0.5
0.5
0.0
0.0
0.0
0
250
500
750
1005
250
500
750
1000
250
520
750
1000
0
250
500
750
1000
250
500
750
1000
Apym. Product
Dot Product
(Outas: Diiszuuntzz Distance
jourzut Oisaano))
(Curpul Distance via coo)
(Dutou: Distanco via Squard)
(Dutput sssounteed D D'stancet Airee feg. Welght
via Sigmo d Ainca. Nog. Weight
Alnos heg. Wilght
ninco Rog. Woight
ince Rog. We gig
3.0
3.5
3.0
0.5
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0
250
500
150
1200
0
250
500
750
1000
230
520
750
1000
250
500
150
1200
250
502
750
1000
Asym. Product
Asym,
(OURH4E Disounted Distance via Sigma d
[iuzzu Dadancs)
(OuIAWEDi22InCS Distance via og)
(Dutou: Dilance via Square) à inog Reg. We geg =5
(Cutput Dosuuntedd Distancet 2 sinea, Reg. Weight =3
&ines Reg. Weggt =3
ance Reg. weight =3
iines Reg. Weight =3
3.0
1.0
3.0
3.0
0.5
D.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
250
500
750
1300
250
500
750
1000
520
750
1000
250
500
750
1000
250
502
750
1000
Figure 16: Grid-world offline Q-learning full results (cont.). Individual plots on show standard deviations.
57


Reviews:
[{"review_id": "S5DbWCGJAmR", "reviewer": "Reviewer_RT4G", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of learning Quasi-metrics is an interesting problem with many applications. The proof of the fact that algorithms invariant to orthogonal transforms can not learn quasimetric functions is quite neat. The formulation of the PQEs is also quite nice. The paper is quite well written as well with toy examples which help pedgogically. \n\nOne complaint I have is that the empirical results are over just 5 trials. ", "summary_of_the_paper": "This paper considers the problem of learning Quasi-metrics. A quasi-metric is a non-negative function of two variables that satisfies the triangle inequality and that d(x,y) = 0 <=> x=y. Unlike metrics it does not satisfy triangle inequality.\n\nIn this paper, the authors define the quasi-metric learning problem. They then proceed to show that algorithms invariant to orthogonal transforms (in a sense they define - such that it includes unconstrained multi-layer perceptron) can not learn transforms satisfy the quasimetric constraints with probability at least 1/2 - o(1). They then define a program called Poisson Quasimetric Embeddings (PQEs) to learn quasimetrics - which come in two related flavours. They conclude with empirical evaluation of PQE and a variety of algorithms.", "summary_of_the_review": "The paper examines an interesting problem. They propose an interesting program to solve the problem, with some analysis to show a class of algorithms can not be used to learn quasimetrics. It is also well written. Hence I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IOrRI2MLf1", "reviewer": "Reviewer_kCMM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am impressed by the long proof of the failure case construction in the appendix. But the statement of the Theorem 4.5 and the base case construction (Figure 3) is confusing. It seems that the orthogonal transformation is not essential in this result. Only thing that matters is that the action is at least nontrivial. Then we can identify different points y ~ y', w ~ w' and do the same trick. \n\nOnce we identify those points, the result becomes obvious: We have a quasimetric in one space, but we cannot define the pushforward of the quasimetric directly to a quotient space. It can fail to be a quasimetric. d(x, y) = d(y, w) = d(w, z) = 1 and d(w, z) = c for c large are just two contradictory statements. You can even get a simpler counterexample by considering d(x, y) = 1 and d(x, y') = c. (If the construction in Figure 3 is allowed, I don't see why this easier one is not allowed.) In other words, if we train an equivariant model on a space where there is actually no equivariance, the model will fail. The author can explain more clearly what Theorem 4.5 means and what are the intended implications.", "summary_of_the_paper": "This paper studies the problem of learning of quasimetrics. It first proves that an orthogonal equivariant model cannot learn quasimetrics reliably, and then proposes the Poisson Quasimetric Embedding model which is both universal and differentiable. To be more precise, the Poisson process (or just a soft modification of Order Embedding) is differentiable and can be used to approximate quasipartitions, and quasipartitions can be used to approximate arbitrary quasimetrics.\n\nThe paper also conducts extensive experiments and indeed PQE has better performance for many tasks.", "summary_of_the_review": "The paper is organized nicely and I have no difficulty following the proof. I think the paper provides a valuable contribution for the learning of quasimetrics and would be useful for many real world applications.\n\nI consider this paper to be marginally above the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HenT5Gnrq9R", "reviewer": "Reviewer_Lnh9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Firstly, the topic under consideration is important and timely. Less structured spaces are frequently encountered, and learning algorithms tend to be developed with very restrictive settings in mind.\n\nOne highlight of the paper is Lemma 4.4, which rules out some common approaches to distance learning for this problem. The proof seems to me to be relatively straightforward. \n\nMy most significant reservation comes from Theorem 5.2, which is the theoretical justification behind the Poisson embedding: There we find a guarantee of distortion O(t log^2 n) for the embedding, and this is exceptionally high. Even the hopeless task of embedding metric space into Euclidean space gives smaller distortion O(logn) by Bourgain's theorem. The authors point to a result of Memoli, but the goal of that paper is quite different than the current one: That paper embeds into an ultrametric - a very restrictive space - and this allows them to  approximate a difficult computational task. So the distortion translates to approximation, which is more reasonable, but even then the dependence on the treewidth is problematic. The task of the current paper is to estimate a distance, and I find that the large distortion undermines this approach.\n\nSome more minor concerns: \n- I'm confused by the statement of Theorem 4.5: What's undesirable about S containing only few pairs? And why should a 50% probability be objectionable? Based on this bound alone, the random embedding could be repeated multiple times until finding one that is a good match for the sample.\n- Why would use test your method against a metric embedding into Euclidean space? That embedding doesn't seem remotely appropriate for the problem under consideration.", "summary_of_the_paper": "The paper is concerned with learning asymmetric distance functions (that is, quasimetrics) from a sample. The authors prove that a certain class of algorithms fails to properly learn these spaces, and instead propose the \"Poisson quasimetric embedding\" as a tool to learn these functions.", "summary_of_the_review": "The paper has some nice positive contributions, but I have concerns about the overall theoretical foundation of the work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6xzBcBKBjT", "reviewer": "Reviewer_WT3X", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n- The paper is well written for most of time. The problem of learning quasimetrics is interesting, and the motivation is clear.\n\n- The large scale experiments in Table 2 and Table 3 look promising. It is interesting to see that in directed networks, the proposed method works fairly well compared to the baselines. \n\nComments:\n\n- It is mentioned in Section 3: \"These objectives also indirectly capture generalization because a predictor with bad approximation or that ignores quasimetric constraints must have large error on some possible pairs.\" Could the authors elaborate on that? \n\n- In particular, is there any relationship between quasimetric violation (Definition 4.2) and the generalization bound?\n\n- If my understanding is correct, the regular (symmetric) metric is no more than a special case of the quasimetric. I wonder if there is any possible explanation for the undirected case (Table 3), in which the proposed method performs worse than some symmetric methods. Is this because of some overfitting on the training network? \n\n- It seems that the acronym NTK is never defined.\n\n- I did not check the proofs.", "summary_of_the_paper": "The paper proposes a Poisson Quasimetric Embedding (PQE) framework, that can be used to embed data to a quasimetric space. Quasimetrics are similar to distance metrics, except that symmetry property does not need to hold. The proposed PQE approach can be solved using gradient based methods. \n\nIn addition, the paper shows that many common learning algorithms provably fail to learn a quasimetric consistent with training data.", "summary_of_the_review": "Overall an interesting paper with solid theoretic and experimental results. I am not an expert in this area though, hence I cannot say how novel the approach is. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper is addressing an interesting problem, and provides a valuable contribution for the learning of quasimetrics and would be useful for many real world applications.
Decision: Accept (Poster)