mlsanityData to 14 Oct 2026

Small Transformers Compute Universal Metric Embeddings

arXiv 2209.06788 ↗First posted 14 Sep 2022cs.LG cs.NE math.COcited by 12

Not on the map. Why?

Abstract (arXiv)

We study representations of data from an arbitrary metric space X in the space of univariate Gaussian mixtures with a transport metric (Delon and Desolneux 2020). We derive embedding guarantees for feature maps implemented by small neural networks called probabilistic transformers. Our guarantees are of memorization type: we prove that a probabilistic transformer of depth about nlog(n) and width about n2 can bi-H"older embed any n-point dataset from X with low metric distortion, thus avoiding the curse of dimensionality. We further derive probabilistic bi-Lipschitz guarantees, which trade off the amount of distortion and the probability that a randomly chosen pair of points embeds with that distortion. If X's geometry is sufficiently regular, we obtain stronger, bi-Lipschitz guarantees for all points in the dataset. As applications, we derive neural embedding guarantees for datasets from Riemannian manifolds, metric trees, and certain types of combinatorial graphs. When instead embedding into multivariate Gaussian mixtures, we show that probabilistic transformers can compute bi-H"older embeddings with arbitrarily small distortion.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 53 of its 153 references that are in the map. First posted on arXiv 14 Sep 2022.

Builds on

53 of 153 references.

References · 53

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  5. 2017Poincar'e Embeddings for Learning Hierarchical Representationscited by 684
  6. 2016Error bounds for approximations with deep ReLU networkscited by 574
  7. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 497
  8. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  9. 2018Hyperbolic Neural Networkscited by 402
  10. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  11. 2019Universal Approximation with Deep Narrow Networkscited by 200
  12. 2018Universality of Deep Convolutional Neural Networkscited by 176
38 more
  1. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
  2. 2015Path-SGD: Path-Normalized Optimization in Deep Neural Networkscited by 120
  3. 2020Geoopt: Riemannian Optimization in PyTorchcited by 114
  4. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  5. 2020Minimum Width for Universal Approximationcited by 94
  6. 2018Embedding Text in Hyperbolic Spacescited by 76
  7. 2019A Wasserstein-type distance in the space of Gaussian Mixture Modelscited by 75
  8. 2018geomstats: a Python Package for Riemannian Geometry in Machine Learningcited by 71
  9. 2020From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clusteringcited by 65
  10. 2020Representation formulas and pointwise properties for Barron functionscited by 62
  11. 2017Multilevel Clustering via Wasserstein Meanscited by 49
  12. 2019Inferring Concept Hierarchies from Text Corpora via Hyperbolic Embeddingscited by 49
  13. 2021HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projectionscited by 47
  14. 2021Universal Approximation Theorems for Differentiable Geometric Deep Learningcited by 41
  15. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  16. 2020Wasserstein Regressioncited by 35
  17. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  18. 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
  19. 2015Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Supportcited by 30
  20. 2020Computationally Tractable Riemannian Manifolds for Graph Embeddingscited by 29
  21. 2020Non-Euclidean Universal Approximationcited by 29
  22. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  23. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  24. 2020Globally Injective ReLU Networkscited by 23
  25. 2020A Fully Hyperbolic Neural Model for Hierarchical Multi-Class Classificationcited by 23
  26. 2021Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approachcited by 23
  27. 2022Heterogeneous manifolds for curvature-aware graph embeddingcited by 23
  28. 2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
  29. 2016Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic spacecited by 21
  30. 2019HyperKG: Hyperbolic Knowledge Graph Embeddings for Knowledge Base Completioncited by 20
  31. 2016Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimizationcited by 11
  32. 2018Variational Wasserstein Clusteringcited by 11
  33. 2021Linear Classifiers in Product Space Formscited by 11
  34. 2018Capacity Control of ReLU Neural Networks by Basis-path Normcited by 10
  35. 2020Hyperbolic Distance Matricescited by 7
  36. 2017Computational Methods for Martingale Optimal Transport problemscited by 6
  37. 2021On Procrustes Analysis in Hyperbolic Spacecited by 5
  38. 2021Universal Regular Conditional Distributionscited by 4

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

12 papers.

  1. 2024Transformers are Universal In-context Learnerscited by 43
  2. 2022Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysiscited by 22
  3. 2023A Brief Survey on the Approximation Theory for Sequence Modellingcited by 15
  4. 2023Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometriescited by 6
  5. 2025Transformers through the lens of support-preserving maps between measurescited by 6
  6. 2024Neural Spacetimes for DAG Representation Learningcited by 5
  7. 2025The Curved Spacetime of Transformer Architecturescited by 5
  8. 2023Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structurescited by 4
  9. 2023Transformers Can Solve Non-Linear and Non-Markovian Filtering Problems in Continuous Time For Conditionally Gaussian Signalscited by 4
  10. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 2
  11. 2024Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spacescited by 0
  12. 2026Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examplescited by 0