mlsanityData to 14 Oct 2026

On the Learning and Learnability of Quasimetrics

arXiv 2206.15478 ↗First posted 30 Jun 2022cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 27 of its 66 references that are in the map. First posted on arXiv 30 Jun 2022.

Builds on

27 of 66 references.

References · 27

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2018Representation Learning with Contrastive Predictive Codingcited by 7,777
  3. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  6. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  7. 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
  8. 2020Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hyperspherecited by 1,405
  9. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 763
  10. 2017Deep Reinforcement Learning that Matterscited by 754
  11. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  12. 2014Deep metric learning using Triplet networkcited by 422
15 more
  1. 2016Input Convex Neural Networkscited by 414
  2. 2018An efficient framework for learning sentence representationscited by 198
  3. 2014Learning Fine-grained Image Similarity with Deep Rankingcited by 190
  4. 2018Hyperbolic Entailment Cones for Learning Hierarchical Embeddingscited by 162
  5. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  6. 2015Order-Embeddings of Images and Languagecited by 113
  7. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  8. 2018The Emergence of Spectral Universality in Deep Networkscited by 74
  9. 2020Model-Based Visual Planning with Self-Supervised Functional Distancescited by 42
  10. 2020An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequalitycited by 24
  11. 2019Hyperbolic Disk Embeddings for Directed Acyclic Graphscited by 21
  12. 2017The Stochastic Shortest Path Problem : A polyhedral combinatorics perspectivecited by 7
  13. 2020Shortest path distance approximation using deep learning techniquescited by 6
  14. 2019Multidimensional Dominance Drawingscited by 1
  15. 2020Nested Subspace Arrangement for Representation of Relational Datacited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 4; 2025: 4; 2026: 5.

15 papers.

Sort:

By area:

  1. 2023Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learningcited by 121
  2. 2024Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Makingcited by 56
  3. 2026Temporal Straightening for Latent Planningcited by 38
  4. 2022Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddingscited by 24
  5. 2025Horizon Generalization in Reinforcement Learningcited by 17
  6. 2025Physics-informed Temporal Difference Metric Learning for Robot Motion Planningcited by 6
  7. 2025Temporal Distance-aware Transition Augmentation for Offline Model-based Reinforcement Learningcited by 6
  8. 2024State Chrono Representation for Enhancing Generalization in Reinforcement Learningcited by 3
  9. 2024Quasimetric Value Functions with Dense Rewardscited by 2
  10. 2026Compositional Transduction with Latent Analogies for Offline Goal-Conditioned Reinforcement Learningcited by 1
  11. 2024QuasiNav: Asymmetric Cost-Aware Navigation Planning with Constrained Quasimetric Reinforcement Learningcited by 0
  12. 2025GOSPA and T-GOSPA quasi-metrics for evaluation of multi-object tracking algorithmscited by 0
3 more
  1. 2026From Connectivity to Rewards: Dense Reward Learning with Directed State Graphscited by 0
  2. 2026ChronoSRL: Temporal Geometry for Self-Supervised Reinforcement Learningcited by 0
  3. 2026Do Better Goal Representations Improve Goal-Conditioned Reinforcement Learning?cited by 0