# Universal Approximation Under Constraints is Possible with Transformers

arXiv: https://arxiv.org/abs/2110.03303 · HTML: https://mlsanity.com/paper/2110.03303/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 96 references that are in the map.
- First posted on arXiv 7 Oct 2021.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [Model-Based Domain Generalization](https://mlsanity.com/paper/2102.11436/) (2021)
- [Error bounds for approximations with deep ReLU neural networks in Ws,p norms](https://mlsanity.com/paper/1902.07896/) (2019)
- [Minimum Width for Universal Approximation](https://mlsanity.com/paper/2006.08859/) (2020)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [The phase diagram of approximation rates for deep neural networks](https://mlsanity.com/paper/1906.09477/) (2019)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [geomstats: a Python Package for Riemannian Geometry in Machine Learning](https://mlsanity.com/paper/1805.08308/) (2018)
- [Neural Network Approximation: Three Hidden Layers Are Enough](https://mlsanity.com/paper/2010.14075/) (2020)
- [Differentiating through the Fr'echet Mean](https://mlsanity.com/paper/2003.00335/) (2020)
- [Approximation Bounds for Random Neural Networks and Reservoir Systems](https://mlsanity.com/paper/2002.05933/) (2020)
- [Probably Approximately Correct Constrained Learning](https://mlsanity.com/paper/2006.05487/) (2020)
- [Universal Approximation Theorems for Differentiable Geometric Deep Learning](https://mlsanity.com/paper/2101.05390/) (2021)
- [Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systems](https://mlsanity.com/paper/1712.00754/) (2017)
- [Equivalence of approximation by convolutional neural networks and fully-connected networks](https://mlsanity.com/paper/1809.00973/) (2018)
- [Elementary superexpressive activations](https://mlsanity.com/paper/2102.10911/) (2021)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Non-Euclidean Universal Approximation](https://mlsanity.com/paper/2006.02341/) (2020)
- [Optimal Transport: Fast Probabilistic Approximation with Exact Solvers](https://mlsanity.com/paper/1802.05570/) (2018)

## Built on by (most cited first, 30 of 32)

- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [HardNet: Hard-Constrained Neural Networks with Universal Approximation Guarantees](https://mlsanity.com/paper/2410.10807/) (2024)
- [Measure-to-measure interpolation using Transformers](https://mlsanity.com/paper/2411.04551/) (2024)
- [Pretrained Language Models as Visual Planners for Human Assistance](https://mlsanity.com/paper/2304.09179/) (2023)
- [Approximation Rate of the Transformer Architecture for Sequence Modeling](https://mlsanity.com/paper/2305.18475/) (2023)
- [Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformer](https://mlsanity.com/paper/2201.13094/) (2022)
- [Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers](https://mlsanity.com/paper/2508.10480/) (2025)
- [On the rate of convergence of a classifier based on a Transformer encoder](https://mlsanity.com/paper/2111.14574/) (2021)
- [A Brief Survey on the Approximation Theory for Sequence Modelling](https://mlsanity.com/paper/2302.13752/) (2023)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Universal Approximation of Mean-Field Models via Transformers](https://mlsanity.com/paper/2410.16295/) (2024)
- [Do ReLU Networks Have An Edge When Approximating Compactly-Supported Functions?](https://mlsanity.com/paper/2204.11231/) (2022)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Structure-Preserving Transformers for Sequences of SPD Matrices](https://mlsanity.com/paper/2309.07579/) (2023)
- [Why self-attention is Natural for Sequence-to-Sequence Problems? A Perspective from Symmetries](https://mlsanity.com/paper/2210.06741/) (2022)
- [Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size](https://mlsanity.com/paper/2502.11467/) (2025)
- [A unified framework for establishing the universal approximation of transformer-type architectures](https://mlsanity.com/paper/2506.23551/) (2025)
- [Large Language Models as Universal Predictors? An Empirical Study on Small Tabular Datasets](https://mlsanity.com/paper/2508.17391/) (2025)
- [Measure-to-measure Regression with Transformers](https://mlsanity.com/paper/2605.28075/) (2026)
- [Sampled Transformer for Point Sets](https://mlsanity.com/paper/2302.14346/) (2023)
- [How Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliability](https://mlsanity.com/paper/2406.12915/) (2024)
- [Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime](https://mlsanity.com/paper/2506.24120/) (2025)
- [Riemannian Liquid Spatio-Temporal Graph Network](https://mlsanity.com/paper/2601.14115/) (2026)
- [Universal Approximation of Measure-to-Measure Operators by Pushforwards](https://mlsanity.com/paper/2609.35483/) (2026)
- [Dynamic Universal Approximation Theory: The Basic Theory for Transformer-based Large Language Models](https://mlsanity.com/paper/2407.00958/) (2024)
- [Automatic Classification of Sleep Stages from EEG Signals Using Riemannian Metrics and Transformer Networks](https://mlsanity.com/paper/2410.19819/) (2024)
- [Geometry-Preserving Neural Architectures on Manifolds with Boundary](https://mlsanity.com/paper/2602.03082/) (2026)
- [Stochastic Dimension Implicit Functional Projections for Global Integral Conservation in High-Dimensional PINNs](https://mlsanity.com/paper/2603.29237/) (2026)
- [Progressive Approximation in Deep Residual Networks: Theory and Validation](https://mlsanity.com/paper/2604.24154/) (2026)
- [Approximation Error Upper and Lower Bounds for H"older Class with Transformers](https://mlsanity.com/paper/2605.07463/) (2026)

## Abstract (arXiv)

Many practical problems need the output of a machine learning model to satisfy a set of constraints, K. Nevertheless, there is no known guarantee that classical neural network architectures can exactly encode constraints while simultaneously achieving universality. We provide a quantitative constrained universal approximation theorem which guarantees that for any non-convex compact set K and any continuous function f:ℝnrightarrow K, there is a probabilistic transformer hatF whose randomized outputs all lie in K and whose expected output uniformly approximates f. Our second main result is a "deep neural version" of Berge's Maximum Theorem (1963). The result guarantees that given an objective function L, a constraint set K, and a family of soft constraint sets, there is a probabilistic transformer hatF that approximately minimizes L and whose outputs belong to K; moreover, hatF approximately satisfies the soft constraints. Our results imply the first universal approximation theorem for classical transformers with exact convex constraint satisfaction. They also yield that a chart-free universal approximation theorem for Riemannian manifold-valued functions subject to suitable geodesically convex constraints.