On the Learning and Learnablity of Quasimetrics
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.