# UNIVERSAL APPROXIMATION UNDER CONSTRAINTS
## IS POSSIBLE WITH TRANSFORMERS


**Anastasis Kratsios[⇤], Tianlin Liu & Ivan Dokmani´c**

Universit¨at Basel,

Departement Mathematik und Informatik
_{firstname.lastname}@unibas.ch_

ABSTRACT


**Behnoosh Zamanlooy[⇤]**
Universit¨at Z¨urich,

Department of Informatics
bzamanlooy@ifi.uzh.ch


Many practical problems need the output of a machine learning model to satisfy
a set of constraints, K. There are, however, no known guarantees that classical
neural networks can exactly encode constraints while simultaneously achieving
universality. We provide a quantitative constrained universal approximation theorem which guarantees that for any convex or non-convex compact set K and any
continuous function f : R[n] _! K, there is a probabilistic transformer_ _F[ˆ] 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 (1963)’s
Maximum Theorem. 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 _F[ˆ] that approximately minimizes L and whose outputs belong to K;_

moreover, _F[ˆ] approximately satisfies the soft constraints. Our results imply the_

first universal approximation theorem for classical transformers with exact convex
constraint satisfaction, and a chart-free universal approximation theorem for Riemannian manifold-valued functions subject to geodesically-convex constraints.


**Keywords: Constrained Universal Approximation, Probabilistic Attention, Transformer Networks,**
Geometric Deep Learning, Measurable Maximum Theorem, Non-Affine Random Projections.

1 INTRODUCTION

In supervised learning, we select a parameterized model _f[ˆ] : R[n]_ _! R[m]_ by optimizing a real-valued

loss function[1]L over training data from an input-output domain X ⇥Y ✓ R[n] _⇥_ R[m]. A necessary
property for a model class to produce asymptotically optimal results, for any continuous loss L,
is the universal approximation property. However, often more structure (beyond vectorial R[m]) is
present in a learning problem and this structure must be encoded into the trained model _f[ˆ] to obtain_

meaningful or feasible predictions. This additional structure is typically described by a constraint
set K R[m] and the condition _f[ˆ](_ ) _K. For example, in classification K =_ _y_ [0, 1][m] :
_m_ _✓_ _X_ _✓_ _{_ _2_

_i=1_ _[y][i][ = 1][}][ (][Shalev-Shwartz & Ben-David][,][ 2014][), in Stackelberg games (][Holters et al.][,][ 2018][;]_

Jin et al., 2020; Li et al., 2021) K is the set of utility-maximizing actions of an opponent, in integer

Pprogramming K is the integer lattice Z[m] (Conforti et al., 2014), in financial risk-management K is

a set of positions meeting the minimum solvency requirements imposed by international regularity
bodies (Basel Committee on Banking Supervision, 2015; 2019; McNeil et al., 2015), in covariance
matrix prediction K ✓ R[m][⇥][m] is the set of m ⇥ _m matrices which are symmetric and positive semi-_
definite (Bonnabel et al., 2013; Bonnabel & Sepulchre, 2009; Baes et al., 2021), in geometric deep
learning K is typically a manifold (e.g. a pose manifold in computer vision and robotics (Ding &
Fan, 2014) or a manifold of distance matrices (Dokmanic et al., 2015)), a graph, or an orbit of a
group action (Bronstein et al., 2017; 2021; Kratsios & Bilokopytov, 2020). Therefore, we ask:

_Is exact constraint satisfaction possible with universal deep learning models?_


_⇤Corresponding authors._

1For example, in a regression problem one can set L(x, y) = kf (x) − _yk for an unknown function f or in_

regression problems one sets L(x, y) = _i=1[[][C][(][x][)]][i][ log(][y][i][)][ for an unknown classifier][ C][.]_

[P][m]


-----

The answer to this question begins by examining the classical universal approximation theorems for
deep feedforward networks. If L and K are mildly regular, the universal approximation theorems of
Hornik et al. (1989); Cybenko (1989); Pinkus (1999); G¨uhring et al. (2020); Kidger & Lyons (2020);

Park et al. (2021) guarantee that for any “good activation function σ” and for every tolerance level
_✏> 0, there is a deep feedforward network with activation function σ, such that inf_ _y_ _K L(x, y) and_
_2_
_L(x,_ _f[ˆ](x)) are uniformly at most ✏_ apart. Written in terms of the optimality set,


_kf[ˆ](x) −_ argminy2K


_L(x, y)k_ _✏,_ (1)


sup

_x2X_


where the distance of a point y R[m] to a set A R[m] is defined by _y_ _A_, inf _a_ _A_ _y_ _a_ .
_2_ _✓_ _k_ _−_ _k_ _2_ _k_ _−_ _k_
Since argminy _K L(x, y)_ _K, then (1) only implies that_ _f[ˆ](x)_ _K_ _✏_ and there is no reason
_2_ _✓_ _k_ _−_ _k _

to believe that the constraint _f[ˆ](x) 2 K is exactly satisfied, for every x 2 X_ .

This kind of approximate constraint satisfaction is not always appropriate. In the following examples
constraint violation causes either practical or theoretical concerns:

(i) In post-financial crisis risk management, international regulatory bodies mandate that any

financial actor should maintain solubility proportional to the risk of their investments (Basel
Committee on Banking Supervision, 2015; 2019). To prevent future financial crises, any
violation of these risk constraints, no matter the size, incurs large and immediate fines.

(ii) In geometric deep learning, we often need to encode complicated non-vectorial structure

present in a dataset, by viewing it as a K valued function (Fletcher, 2013; Bonnabel &
Sepulchre, 2009; Baes et al., 2021). However, if K is non-convex then Motzkin (1935)
confirms that there is no unique way to map predictions _f[ˆ](x) 62 K to a closest point in_

_K. Thus, we are faced with the dilemma: either make an ad-hoc choice of a k in K with_
_k ⇡_ _f[ˆ](x) (ex.: an arbitrary choice scheme when K = Z[m]) or have meaningless predictions_

(ex: non-integer values to integer programs, or symmetry breaking (Weinberg, 1976)[2]).


Constrained learning was recognized as an effective framework for fairness and robustness by Chamon & Ribeiro (2020) who study empirical risk minimization under constraints. Many emerging
topics in machine learning lead to constrained learning formulations. A case in point is modelbased domain generalization (Robey et al., 2021). Despite the importance of (deep) learning with
constraints, there are no related approximation-theoretic results to the best of our knowledge.

In this paper, we bridge this theoretical gap by showing that universal approximation with exact
constraint satisfaction is always possible for deep (probabilistic) transformer networks with a single
attention mechanism as output layer. Our contribution is three-fold:

1. We derive the first universal approximation theorem with exact constraint satisfaction;
2. Our transformer network’s encoder and decoder adapt to the dimension of the constraint

set and thus beat the curse of dimensionality for low-dimensional constraints;

3. Our models leverage a probabilistic attention mechanism that can encode non-convex con
straints. This probabilistic approach is key to bypass the topological obstructions to nonEuclidean universal approximation (Kratsios & Papon, 2021).


Our analysis provides perspective on the empirical success of attention and adds to the recent line
of work on approximation theory for transformer networks, (Yun et al., 2020a;b), which roughly
considers the unconstrained case (with K in (1) replaced by R[m]) in the special case of L(x, y) =
_kf_ (x)−yk for a suitable target function f : R[n] _! R[m]. Our probabilistic perspective on transformer_
networks fits with the representations of Vuckovic et al. (2021) and of Kratsios (2021).

Our results can be regarded as an approximation-theoretic counterpart to the constrained statistical
learning theory of Chamon & Ribeiro (2020). Further, they put forward a perspective on randomness in neural networks that is complementary to the work of Louart et al. (2018); Gonon et al.
(2020a;b). We look at the same problem focusing on constraint satisfaction instead of training efficiency. Finally, our proof methods are novel, and build on contemporary tools from metric geometry
(Ambrosio & Puglisi, 2020; Bru`e et al., 2021).

2As discussed in Rosset et al. (2021) this is problematic since respecting symmetries can often massively

reduce the computational burden of a learning task.


-----

1.1 THE PROBABILISTIC ATTENTION MECHANISM

We now give a high-level explanation of our results; the detailed formulations are in Section 2.

Introduced in (Bahdanau et al., 2015) and later used to define the transformer architecture (Vaswani
et al., 2017), in the NLP context, attention maps a matrix of queries Q, a matrix of keys K, and a
matrix of values V to the quantity Softmax(QK _[>])V, where the softmax function (defined below) is_
applied row-wise to QK _[>]. Just as the authors of (Petersen & Voigtlaender, 2020; Zhou, 2020) focus_
on the simplified versions of practically implementable ConvNets in the study of approximation
theory of deep ConvNets (e.g. omitting pooling layers), we find it sufficient to study the following
simplified attention mechanism to obtain universal approximation results:


Attention (w, Y ), SoftmaxN (w)[>] _Y =_



[SoftmaxN (w)n]Yn, (2)

_n=1_

X


_e[wk]_
where w R[N], SoftmaxN : R[N] _w_ ( _N_ _k=1[, and][ Y][ is an][ N][ ⇥]_ _[m][ matrix. The attention]_
_2_ _3_ _7!_ _j=1_ _[e][wj][ )][N]_

mechanism (2) can be interpreted as “paying attention” to a set of particlesP _Y1, . . ., YN_ R[m] defined
by Y ’s rows. This simplified form of attention is sufficient to demonstrate that transformer networks 2
can approximate a function while respecting a constraint set, K, whether convex or non-convex.

**Informal Theorem 1.1 (Deep Maximum Theorem for Transformers). If K is convex and the quan-**
_tities defining (1) are regular then, for any ✏_ _2 (0, 1], there is a feedforward network_ _f[ˆ], an X✏_ _⇢_ R[n]

_of probability 1-✏, and a matrix Y such that the transformer Attention( f[ˆ](x), Y ) satisfies:_

_(i) Exact Constraint Satisfaction: For each x 2 R[n], Attention( f[ˆ](x), Y )2 K,_

_(ii) Universal Approximation: supx2X✏_ _k Attention( f[ˆ](x), Y ) −_ argminy[?]2K _L(x, y[?])k_ _✏_


Informal Theorem 1.1 guarantees that simple transformer networks can minimize any loss function
while exactly satisfying the set of convex constraints. As illustrated by Figure 1 and Figure 2, K’s
convexity is critical here, since without it the transformer’s prediction may fail to lie in K. This is
because any transformer network’s output is a convex combinations of the particles Y1, Y2, Y3; thus,
any transformer network’s predictions must belong to these particles’ convex hull.

ibid


Figure 1: Convex Constraints Figure 2: Non-Convex Constraints

In Figures 1 and 2, Y ’s columns, i.e. the particles Y1, Y2, and Y3, are each illustrated by a at the
_•_
constraint set (K) vertices. The bubble around each each Yi illustrates the predicted probability,
for a given input, that f (x) is nearest to that Yi. The is the transformer’s prediction which is,
**_⇥_**
by construction, a convex combination of the Yi weighted by the aforementioned probabilities and
therefore they lie in the K if it is convex (Figure 1) but not if K is non-convex (Figure 2).

Naturally, we arrive at the question: How can (i) and (ii) simultaneously hold when K is non-convex?

Returning to Vaswani et al. (2017) and using the introduced terminology, we note that the role of
the SoftmaxN layer is to rank the importance of the particles {Yn}n[N]=1 [when optimizing][ L][, at any]

given input: the weights [SoftmaxN (w)]n in (2) can be interpreted as charging their respective point
_masses {δYn_ _}n[N]=1_ [with probabilities of being optimal for][ L][ (relative to the other particles)][3][. This]

suggests the following probabilistic reinterpretation of attention (which we denote by p-attention):


P-attention(w, Y ),



[SoftmaxN (w)]nδYn _._ (3)

_n=1_

X


3Following Villani (2009), δYn is the Borel probability measure on Rm assigning full probability to any

Borel subset of R[m] containing the particle Yn and 0 otherwise.


-----

Crudely put, P-attention(·, Y ) “pays relative attention to the particles” Y1, . . ., Yn 2 R[m].

A simple computation shows that the mean prediction of our probabilistic attention mechanism,
exactly implements “classical” Attention of Vaswani et al. (2017), as defined in (2),

Attention(w, Y ) = EX⇠P-attention(w,Y )[X], (4)

where EX⇠P-attention(w,Y )[X] denotes the (vector-valued) expectation of a random-vector X distributed according to P-attention(w, Y ). Hence, (3) is no less general than (2). The advantage
of (3) is that, if each particle Yn belongs to K (even if K is non-convex) then, any sample drawn
from the probability measure P-attention(w, Y ) necessarily belongs to K.

1.2 QUALITATIVE RESULTS: DEEP MAXIMUM THEOREM

Probabilistic attention (3) yields the following non-convex generalization of Informal Theorem 1.1.
The result is a qualitative universal approximation theorem as well as a deep neural version of the
Maximum Theorem[4] (Berge, 1963), which states that under mild regularity conditions, given any
well-behaved family of input dependent “soft constraint sets” {Cx}x2Rn compatible with K, there
is a measurable function mapping each x 2 R[n] to a minimizer of L(x, y) on K \ Cx.

We use W1 to denote the Wasserstein-1 distance between probability measures on K. The results also give the flexibility to the user to enforce an input-dependent family of “soft constraints”
_{Cx}x2Rn which only need to hold approximately; definitions are provided in Section 1.4._
**Informal Theorem 1.2 (Deep Maximum Theorem: Non-Convex Case). If the quantities defining 1**
_are regular, K is a compact set of “exact constraints”, and {Cx}x2Rn a set of “soft constraints”,_
_then, for any approximation quality 0 < ✏_ __ 1, there is a deep feedforward network _f[ˆ] and a matrix_

_Y satisfying:_

_(i) Exact Constraint Satisfaction: For each x 2 R[n], P-attention( f[ˆ](x), Y ) is supported in K,_

_(ii) Universal Approximation: P(W1(P-attention( f[ˆ](x), Y ), argminy[?]2Cx\K_ _L(x, y[?])) _ _✏) ≥_ 1 − _✏;_

_where for a probability measure P on R[m]_ _and a B_ R[m] _we define W1(P, B), inf_ _b_ _B W1(P, δb)._
_✓_ _2_
**Example 1.3 (Reduction to Classical Point-to-Set Distance). In particular, when P is a point-mass**
P = δy for some y 2 R[m], then one recovers the familiar Euclidean distance to the set B via:

(def) (def)

_W1(δy, B)_ = inf = _y_ _B_ ;

_b_ _B_ _[W][1][(][δ][y][, δ][b][) = inf]b_ _B_ _k_ _−_ _k_
_2_ _2_ _[k][y][ −]_ _[b][k]_

_where the first and second equality follows from (Villani, 2009, (5) - page 99), and the last equality_
_is the definition of ky −_ _Bk (as in (Aubin & Frankowska, 2009, Definition 1.1.1))._

Another important class of non-convex constraints arising from geometric deep learning where K is
a non-Euclidean ball in a Riemannian submanifold of R[m]. In this broad case, we may extract mean
predictions from P-attention( f, Y[ˆ] ), by applying the Fr´echet mean introduced in Fr´echet (1948).

Such “geometric means” are well-understood theoretically (Bhattacharya & Patrangenaru, 2003)
and easily handled numerically Miolane et al. (2020); Lou et al. (2020).

1.3 QUANTITATIVE RESULTS: CONSTRAINED UNIVERSAL APPROXIMATION THEOREM


In its current form, the objective function L is too general to derive quantitative approximation
rates[5]. Nevertheless, as with most universal approximation theorems (Hornik et al., 1989; Pinkus,
1999; Kidger & Lyons, 2020), if each soft constraint Cx is set to R[m] and L quantifies the uniform
distance to an unknown continuous function f : R[n] _! K in the Euclidean sense,_

_L(x, y), kf_ (x) − _yk,_

then, Informal Theorem 1.2 reduces to a (qualitative) universal approximation for transformer networks with exact constraint satisfaction. In fact, this additional structure is enough for us to derive
quantitative versions of the aforementioned results. We permit ourselves the general situation, where

4More precisely, our result is a deep neural version of the measure-theoretic counterpart to Berge’s Maxi
mum Theorem; see (Aliprantis & Border, 2006, (Measurable Maximum Theorem) - Theorem 18.19).

5For instance, L can describe anything from a regression, to a clustering problem.


-----

1

_K is contained in an unknown d-dimensional submanifold (where d 2 ⇥(m_ _s ) for some s > 0)._

Our approximation rates scale favourably in the ratio s ⇡ [log(]log([m]d)[)] [; i.e., we avoid the curse of dimen-]

sionality for low-dimensional constraint sets. This additional structure translates into the familiar
encoder-decoder structure deployed in most transformer network implementations.

Figure 3: Encoder : ⇡ _f_ Figure 4: Decoder : ⇡ Random Projection to K

Figure 3 illustrates the encoder network _E[ˆ] : R[n]_ _! R[m], whose role is to perform a (classical)_

unconstrained approximation of the target function, f . Since _E[ˆ] is a classical feedforward network_

then its approximation of the target function can be arbitrarily close to the constraint set K but it
need not lie in it. The next step is to “map the encoder network’s output onto K with low distortion.”
The role of the decoder network _D[ˆ] is to correct any constraint violation made by encoder network by_

“projecting them back on to K”. However, such a projection does not exist if K is not convex since
there must be more than one closest point in K to some y 2 R[m] (Motzkin, 1935). Nevertheless,
if the “projection” were capable of mapping any y 2 R[m] to multiple points on K, ranked by their
proximity to y, then there would be no trouble. The decoder network accomplishes precisely this, as
illustrated in Figure 4, where the bubbles illustrate the probability of any particle in K being closest
to y, illustrated by the size of the bubbles in Figure 4. Mathematically,[6][ ˆ]D : R[m] _! P1(K) approx-_

imates a (non-affine) random projection, in the sense of Ohta (2009); Ambrosio & Puglisi (2020);
Bru`e et al. (2021); i.e.: a 1-Lipschitz map ⇧: R[m] _! P1(K) satisfying the random projection_

_property: for all y 2 K_

⇧y = δy.

Thus, ⇧’s random projection property means that it fixes any output already satisfying the constraint
_K, and its Lipschitz regularity implies that it is stable. Thus, sampling from ⇧(y1) is similar to_
sampling from ⇧(y2) whenever the points y1, y2 2 R[m] are near to one another.

**Remark 1.4. Random projections are closely tied to the (random) partitions of unity of Lee & Naor**
_(2005) (see (Ambrosio & Puglisi, 2020, Theorem 2.8)). These random projections generalize the_
_random projections of Johnson & Lindenstrauss (1984), beyond the case where K is affine._

**Remark 1.5. The special case of random projections onto affine spaces has recently been used when**
_constructing universal neural models (Cuchiero et al., 2021; Puthawala et al., 2020)._

We record the complexity of both the decoder and encoder networks constructed in our quantitative
results in Table 1. Here A, B, C, D ≥ 0 are constants independent of ✏ and k, where k 2 N+ is
the number of continuous derivatives which f admits (when viewed as a function into R[m]). From

|Network|ˆ ˆ E D|
|---|---|


|Depth Width N Q|O(m1 s (1 + ✏3(k2 nn +1) −kn2n +1 )) O⇣ (N3 2 (A + 2✏)(4 −✏−1)2)2 sm⌘ m1 s (4n + 10) m1 s + N + 2 - O%(✏−1A + B)m 2 & O⇣ sm⌘ - ✏−|
|---|---|



Table 1: Complexity of simple transformer network1 _mf[ˆ] = D ◦[ˆ]_ _E[ˆ] approximating2m_ _m f_ .

Table 1, we see that if m _s ⌧_ _m then, s > 0 is large; hence, ✏_ _s, (1_ _−_ 4✏[−][1]) _s, and N_ _s are small._

1.4 NOTATION AND BACKGROUND

**Optimal Transportd** Given any non-empty subset K ✓ R[m], the set of all Borel probability

measures P on K with a finite mean; i.e.: EX⇠P[kXk] < 1, is denoted by P1(K). Wasserstein


6P1(K) denotes the Wasserstein space on K, and is defined formally below.


-----

_distance W1 is defined for any P, Q 2 P1(K) by the minimal energy needed to transport all mass_
from P to Q. Following Villani (2009), W1(P, Q) is defined by:

_W1(P, Q), inf_

_⇡_ [E][(][X][1][,X][2][)][⇠][⇡][[][k][X][1][ −] _[X][2][k][]][,]_

where the infimum is taken over all Borel probability measures ⇡ on K [2] with marginals P and Q.
The metric space (P1 (K), W1) is named the Wasserstein space over K; we abbreviate it by P1 (K).
**Smooth Function Spaces** The set of real-valued continuous functions on R[n] is denoted by C(R[n]).

Let k 2 N+ and X ✓ [0, 1][n] be non-empty. The set of functions f : X ! K for which there is
a k-times continuously differentiable f : R[n] R[m] extending f ; i.e.: f = f, is denoted by
_!_ _|X_
_Ctr[k]_ [(][X] _[, K][)][. Our interest in][ C]tr[k]_ [(][X] _[, K][)][ does not stem from the fact that it contains all smooth func-]_

tions mapping [0, 1][n] to K, but rather that it allows us to speak about the uniform approximation of
discontinuous K-valued functions on regions in [0, 1][n] where they are “regular”. This is noteworthy
for pathological constraint sets, such as integer constraints[7]. For details on Ctr[k] [(][X] _[, K][)][, see (][Brudnyi]_

& Brudnyi, 2012a;b) and the extension theorems of Whitney (1934); Fefferman (2005).
**Neural Networks** It has recently been observed that deep feedforward networks with multiple

activation functions, or more generally parametric families of activation functions, achieved significantly more efficient approximation rates than classical feedforward networks with a single activation function (Yarotsky & Zhevnerchuk, 2020; Yarotsky, 2021; Shen et al., 2021a;b). Practically
deployed examples of parametric activation functions are the PReLU activation function of He et al.
(2015), the Sigmoid-weighted Linear Unit (SiLU) of Elfwing et al. (2018), and the Swish activation
function of Ramachandran et al. (2018). We also observe a similar phenomenon, and therefore our
quantitative results consider deep feedforward networks whose activation functions belongs to a 1parameter family σ?, {σt}t2[0,1] ✓ _C(R). The set of all such networks is denoted by NN_ _[σ]n,N[?]_ [and]

it includes all _f[ˆ] : R[n]_ _! R[N]_ with iterative representation:

_fˆ(x), A[(][J][)]x[(][J][)],_ _x[(]ij[j][+1)]_, σtij ((A[(][j][)]x)ij + b[(]ij[j][)][)][,] _x[(0)]_, x, (5)

where x 2 R[n], j = 1, . . ., J − 1, each A[(][j][)] is a dj ⇥ _dj+1-matrix, each b[(][j][)]_ _2 R[d][j][+1]_, dJ+1 = N,
_d1 = 0, t1,1, . . ., tJ,NJ_ [0, 1], for each j. The integer J is _f[ˆ]’s depth and_ max _f_ ’s width.
_2_ _j=1,...,J+1[d][j][ is][ ˆ]_

**Example 1.6 (Networks with Untrainable Nonlinearity). Denote σ, σ0. The subset of classical**
_feedforward networks consisting of all_ _f[ˆ] 2 NN_ _[σ]n,N[?]_ _[with each][ σ][t]ij_ [=][ σ][ in][ (][5][)][ is denoted][ NN][ σ]n,N _[.]_

It is approximation theoretically advantageous to generalize the proposed definition of probabilistic
attention in the introduction (3) by replacing Y with a 3-dimensional array (elementary 3-tensor).
**Definition 1.7 (Probabilistic Attention). Let N, Q, m 2 N+, and Y be an N ⇥** _Q ⇥_ _m-array with_
_Yn,q_ _K for n = 1, . . ., N_ _, q = 1, . . ., Q. Probabilistic attention is the function:_
_2_


R[n] _w_ P-attention(w, Y ), [1]
_3_ _7!_ _Q_


SoftmaxN (w)nδYn,q 2 P1 (K) .


_n=1_


_q=1_


If Y is an N ⇥m-matrix, as in (3), then we identify Y as the N ⇥m⇥1-array in the obvious manner.
**Set-Valued Analysis:** A family of non-empty subsets {Cx}x2R[n] of K is said to be a weakly

_measurable correspondence, denoted C : R[n]_ ◆ R[m], if for every open subset[8]U ✓ _K, {x 2 R[n]_ :
_Cx \ U 6= ;} is a non-empty Borel subset of R[n]_ (Aliprantis & Border, 2006, pages 557, 592).

2 MAIN RESULTS

We now present our main results in detail. All proofs are relegated to the paper’s appendix.

2.1 QUALITATIVE APPROXIMATION: DEEP MAXIMUM THEOREM

Our main qualitative result is the following deep neural version of Berge (1963)’s Maximum Theorem where, the measurable selector is approximately implemented by a probabilistic transformer

7For example, there is no non-constant continuous function f : [0, 1] ! Z. However, for any λ 2 (0, 12 [)]

and any8Since y1 K, y is equipped with its subspace topology, then an open subset2 2 Z, f = y1I[0,λ] + y2I[λ+ 12 _[,][1]][ belongs to][ C]tr[k]_ [([0][, λ][]][ [][ [][λ][ +] U[ 1] of2 _[,][ 1]] K[,][ Z] is any subset of[)][ for each][ k][ 2][ N] R[+]m[.] of the_

form U = U1 \ K where U1 is an open subset of R[m] (see (Munkres, 2000, Lemma 16.1) for further details).


-----

network. We first present the general qualitative result which gives a concrete description of a measurable selector of (1), with high-probability, which has the key property that all its predictions
satisfy the required constraints defined by K.
**Assumption 2.1 (Kidger & Lyons (2020)). σ : R ! R is continuous, σ is differentiable at some**
_x0 2 R, and its derivative satisfies σ[0](x0) 6= 0._
**Theorem 2.2 (Deep Maximum Theorem). Let σ satisfy Assumption 2.1. Let K ✓** R[n] _be a non-_
_empty compact set, C : R[n]_ ◆ R[m] _be a weakly-measurable correspondence with closed values such_
_that Cx \ K 6= ; for each x 2 R[n], L 2 C(R[m]), and P be a Borel probability measure on R[n]._
_For each 0 < ✏_ __ 1, there is an N 2 N+, an _f[ˆ] 2 NN_ _[σ]n,N_ _[of width at most][ 2 +][ n][ +][ N]_ _[, and an]_

_N ⇥_ _m-matrix Y such that:_

_Fˆ : R[n]_ _3 x 7! P-attention_ _fˆ(x), Y_ _2 P1(R[m]),_ (6)

_satisfies the following:_ ⇣ ⌘

_(i) Exact Constrain Satisfaction: [x2Rn supp( F[ˆ](x)) ✓_ _K,_

_(ii) Probably Approximately Optimality: There is a compact X✏_ _✓_ R[n] _satisfying:_

_(a) max_ _F_ (x), argmin _L(x, y))_ _✏,_

_x2X✏_ _[W][1][( ˆ]_ _y2Cx\K_ __

_(b) 1 −_ P(X✏)  _✏._

Theorem 2.2 implies that for any random field (Y _[x])x2Rn on R[m]_ (i.e. a family of R[m]-valued random
vectors indexed by R[n]) with Y _[x]_ _⇠_ _F[ˆ](x): 1. samples drawn from Y_ _[x]_ are in K (by (i)) and 2.

samples drawn from each Y _[x]_ are near to the optimality set argminy _Cx_ _K L(x, y) (by (ii))._
_2_ _\_

**Corollary 2.3 (F[ˆ]’s Mean Prediction). Assume the setting of Theorem 2.2. Let {Y** _[x]}x2Rn be a_

_K-valued random field with Y_ _[x]_ _⇠_ _F[ˆ](x) for each x 2 R[n]_ _then, 1 −_ P(X✏)  _✏_ _and_

max _L(x, y[?])_ ] _✏._
_x2X✏_ [E][[][k][Y][ x][ −] _y[argmin][?]2Cx\K_ _k_ __

Appendix 8 contains additional consequences of the Deep Maximum Theorem, such as the special
case of classical transformers when K is convex. Next, we complement our qualitative results by
their quantitative analogues, within the context of universal approximation under constraints.
2.2 QUANTITATIVE APPROXIMATION: CONSTRAINED UNIVERSAL APPROXIMATION

In order to derive a quantitative constrained universal approximation theorem, we require the loss
function to be tied to the Euclidean norm in the following manner.
**Assumption 2.4 (Norm-Controllable Loss). There is a continuous f : R[n]** _! R[m]_ _with f_ (R[n]) ✓ _K_
_and a continuous l : [0, 1) ! [0, 1) with l(0) = 0, satisfying: L(x, y) _ _l(kf_ (x) − _yk)._

Just as with transformer networks, our “constrained universal approximation theorem” approximates
a suitably regular function f : R[n] _! K ✓_ R[m] while exactly respecting the constraints K by
implementing an encoder-decoder network architecture. Thus, our model is a composition of an
_encoder network_ _E[ˆ] : R[n]_ _! R[d]_ whose role is to approximate f in a classical “unconstrained fashion”

and a decoder network (with probabilistic attention layers at its output) _D[ˆ] : R[d]_ _! P1(K) whose role_

is to enforce the constraints K while preserving the approximation performed by _E[ˆ], where d n m._

To take advantage of the encoder-decoder framework present in most transformer networks, we
formalize what is often called a “latent low-dimensional manifold” hypothesis. Briefly, this means
that, the hard constraints in set K are contained in a “low dimensional” subspace.
**Assumption 2.5 (Low-Dimensional Manifold). There is an 0 < s and a smooth bijection Φ from**

1

R[n] _to itself with smooth inverse[9], such that Φ(K) ✓_ R[d]; where 2  _d and d 2 ⇥(m_ _s )._

Assumption 2.5 does not postulate that K is itself a single-chart low-dimensional manifold, or even
a manifold. Rather, K need only be contained in a low-dimensional manifold. For the fast rates we
use activation functions generalizing the swish function (Ramachandran et al., 2018) as follows.
**Assumption 2.6 (Swish-Like Activation Function). The map σ : [0, 1] ⇥** R 3 (↵, t) 7! σ↵(t) 2 R
_is continuous; σ0 is non-affine and piecewise-linear, and σ1 is smooth[10]_ _and non-polynomial._

9Here smooth means that Φ is continuously differentiable any number of times. NB, smooth bijections with

smooth inverses are called diffeomorphisms in the differential geometry and differential topology literature.

10Following Jost (2017), a function σ : R ! R is called smooth (or class C _1) if @kσ exists for each k 2 N+._


-----

**Theorem 2.7 (Constrained Universal Approximation). Let k 2 N+ and X ✓** [0, 1][n] _be non-empty._
_Suppose that σ satisfies 2.6, L satisfies Assumption 2.4, K ✓_ R[n] _is non-empty, compact and sat-_
_isfies Assumption 2.5. For any f_ _Ctr[k]_ [(][X] _[, K][)][, every constraining quality][ ✏][K]_ _[>][ 0][, and every]_
_2_

_approximation error ✏f > 0, there exist N, Q 2 N+, an encoder_ _E 2 NN[ˆ]_ _[σ]n,d[, and a decoder:]_


_Dˆ : R[d]_ _3 x 7!_


1(K) (7)
_2 P_


P-attention


_Dˆ_ (x), Y


_k=1_


_where_ _D[ˆ]_ _[σ]d,N_ _[and][ Y][ is an][ N][ ⇥]_ _[Q][ ⇥]_ _[m][-array with][ Y][1][,][1][, . . ., Y][N,Q]_
_2 NN_ _[2][ K][ such that:]_

_(i) Exact Constrain Satisfaction: For each x 2 R[n]: supp( D ◦[ˆ]_ _E[ˆ](x)) ✓_ _K,_

_(ii) Universal Approximation: The estimate holds_ [11] _:_

_x_ sup[0,1][n][ W][1][( ˆ]D ◦ _E[ˆ](x), argminy_ _K_ _L(x, y)) _ _✏K + k Lip(Φ[−][1])d✏f_ ;
_2_ _2_

_where, 0 < k is an absolute constant independent of n, m, d, f_ _, and of ✏_ _and Lip(Φ[−][1]) denotes_
_the Lipschitz constant of Φ[−][1]_ _on the compact set {z 2 R[d]_ : kz − Φ(K)k  _✏f_ _}._

_Furthermore, the “complexities” of_ _D[ˆ] and_ _E[ˆ] are recorded in Table[12]_ _1 for_ 2[✏] [=][ ✏][k][ =][ ✏][f] _[.]_

In practice, we can only sample from each measure _D◦[ˆ]_ _E[ˆ](x). In this case, we may ask how the typical_

sample drawn from a random-vector Y _[x]_ distributed according to our learned measure _D ◦[ˆ]_ _E[ˆ](x)_

performs when minimizing L(x, y). The next result relates the estimates in Theorem 2.7 (ii) to the
typical (in Y _[x]) worst-case (in x) gap between a sample from Y_ _[x]_ and f (x), as quantified by L(x, ·).
**Corollary 2.8 (Average Worst-Case Loss). Assume the setting of Theorem 2.7 and suppose that the**
_“modulus” l in Assumption 2.4 is strictly increasing and concave. Let_ _D[ˆ] and_ _E[ˆ] be as in Theorem 2.7_

_and let_ _Y_ _[x]_ _x_ _be an R[m]-valued random field with Y_ _[x]_ (x), for each x R[n]. Then:
_{_ _}_ _2X_ _⇠_ _D ◦[ˆ]_ _E[ˆ]_ _2_

maxx [E][Y][ x][⇠]D◦[ˆ] _E[ˆ](x)_ [[][L][(][x, Y][ x][)]][ ] _[l]_ _✏K + k Lip(Φ[−][1])d✏f_ _._

_2X_

Corollary 2.8 quantifies the expected performance of a sample from our probabilistic transformer% &
model, as expressed by L, whereas Theorem 2.7 (ii) quantifies the difference from the transformer’s
prediction to the optimal prediction value. Next, we consider implications of our main results.
2.3 APPLICATIONS

We apply our theory to obtain a universal approximation theorem for classical transformer networks
with exact convex constraint satisfaction and to derive a version of the non-Euclidean universal approximation theorems of Kratsios & Bilokopytov (2020); Kratsios & Papon (2021) for Riemannianmanifold valued functions which does not need explicit charts. As with most quantitative (uniform)
universal approximation theorems (G¨uhring et al., 2020; Kidger & Lyons, 2020; Shen et al., 2021a),

we henceforth consider L(x, y) = kf (x) − _yk. We also fix f 2 Ctr[k]_ [([0][,][ 1]][n][, K][)][.]

2.3.1 TRANSFORMERS ARE CONVEX-CONSTRAINED UNIVERSAL APPROXIMATORS

We return to the familiar transformer networks of Vaswani et al. (2017). The next result shows that
transformer networks can balance universal approximation and exact convex constraint satisfaction.
This is because when K is convex, then the mean of the random field {Y _[x]}x2Rn of Corollary 2.3_
must belong to K. Consequently, the identity (4) implies that Attention( D ◦[ˆ] _E[ˆ](·), Y ) ⇡_ _f_ .

**Corollary 2.9 (Constrained Universal Approximation: Convex Constraints). Consider the setting**
_and notation of Corollary 2.8. Suppose that K is convex and let L(x, y) = kf_ (x) − _yk. Then:_

R[n] _3 x 7! E[Y_ _[x]] = Attention( D ◦[ˆ]_ _E[ˆ](x), Y ) 2 K;_ (8)

_(i) Exact Constraint Satisfaction: EY x_ ˆ (x)[[][Y][ x][]][ 2][ K][, for each][ x][ 2][ R][n][,]
_⇠D◦E[ˆ]_

_(ii) Universal Approximation: sup[0,1]n kf_ (x) − EY x⇠D◦ˆ _E[ˆ](x)[[][Y][ x][]][k][ < ✏][K][ +][ kd✏][f]_ _[.]_

_The “complexities” of the networks_ _D[ˆ] and_ _E[ˆ] are recorded in Table_ [13] _1 for_ 2[✏] [=][ ✏][k][ =][ ✏][f] _[.]_

11In fact, we actually prove that the slightly stronger statement: supx2[0,1]n W1 _D ◦ˆ_ _E[ˆ](x), δf_ (x) __ _✏K +_

_k Lip(Φ[−][1])d✏f_ . Both formulations align when l has a unique minimum at 0, as is the case when⇣ _L⌘(x, y) =_
_kf12(xExplicit constants are recorded in Table) −_ _yk? and k · k? is any norm on R[m]. 2 within the paper’s appendix; there, ✏K and ✏f may differ._

13Explicit constants are recorded in Table 2 within the paper’s appendix; there, ✏K and ✏f may differ.


-----

2.3.2 CHART-FREE RIEMANNIAN MANIFOLD-VALUED UNIVERSAL APPROXIMATION

We explore how additional non-convex structure of the constraint set K can be encoded by the
_probabilistic transformer networks of Theorems 2.2 and 2.7 and be used to build new types of (de-_
terministic) transformer networks. These results highlight that the standard transformer networks
of (8) are specialized for convex constraints and that by instead using an intrinsic variant of expectation, we build can new types of “geometric transformer networks” customized to K’s geometry.
This section makes use of Riemannian geometry; for an overview see Jost (2017).

Let (M, g) be a connected d-dimensional Riemannian submanifold of R[m] with distance function
by dg. We only require the following mild assumption introduced in Afsari (2011). We recall that
the injectivity radius at y0, denoted by inf _g(y0), (see (Jost, 2017, Definition 1.4.6)) is the minimum_
length of a geodesic (or minimal length curve) in M with starting point y0. We also recall that the
_sectional curvature (see (Jost, 2017, Definition 4.3.2) for a formal statement) quantifies the curvature_
of (M, g) as compared the geometry of its flat counterpart R[d]. We focus on a broad class of nonconvex constrains, namely geodesically convex constraints, which generalize convex constraint and
have received recent attention in the optimization literature (Zhang & Sra, 2016; Liu et al., 2017).
**Assumption 2.10 (Geodesically Convex Constraints). The Riemannian manifold (M, g) is con-**
_nected, it is complete as a metric space, and all its sectional curvatures of (M, g) are all bounded_
_above by a constant C ≥_ 0. The non-empty constrain set K satisfies:

_1. Ky0 is contained in the geodesic ball M and some radius ⇢_ _satisfying B[14]:( 0y0 < ⇢<, ⇢), { 2[−]y 2[1]_ min M :inj dg(gy(0y)0,, yp⇡)C < ⇢} for some point

_2. For each 2_ _y0, y1 2 K there exists a unique geodesic γ : [0, 1]{_ _! K joining[}] y[,]_ 0 to y1.

Our latent probabilistic representation grants us the flexibility of replacing the usual “extrinsic mean”
used in (8) to extract deterministic predictions from our probabilistic transformer networks via an
additional Fr´echet mean layer at their readout. This intrinsic notion of a mean, was introduced

independently in Fr´echet (1948) and in Karcher (1977), and is defined on any P 2 P1(K) by:

P¯, argmin _d[2]g[(][k, u][)][ P][(][du][)][.]_ (9)

_k2K_ Z

With this “geometric readout layer” added to our model, we obtain the following variants of our
main results in this non-convex, but geometrically regular, setting.
**Corollary 2.11 (Constrained Universal Approximation: Riemannian Case). Consider the setting**
_and notation of Corollary 2.8. Let L(x, y) = kf_ (x) − _yk. If Assumption 2.10 holds then:_

R[n] _3 x 7!_ _D ◦[ˆ]_ _E[ˆ](x) 2 K,_ (10)

_is a well-defined Lipschitz-continuous function, and the following hold:_

_(i) Exact Constraint Satisfaction:_ _D ◦[ˆ]_ _E[ˆ](x) 2 K, for each x 2 X_ _,_

_(ii) Universal Approximation: sup_ _dg(f_ (x), [ˆ] (x)) < ✏K + kd✏f _._
_X_ _D ◦_ _E[ˆ]_

_The “complexities” of_ _D[ˆ] and_ _E[ˆ] are recorded in Table[15]_ _1 for_ 2[✏] [=][ ✏][k][ =][ ✏][f] _[.]_

3 DISCUSSION


In this paper, we derived the first constrained universal approximation theorems using probabilistic
reformation of Vaswani et al. (2017)’s transformer networks. The results assumed both a quantitative
form (Theorem 2.7) and a qualitative form in the more general case of an arbitrary loss functions L
and additional compatible soft constraints in (Theorem 2.2). Our results provide (generic) direction
to end-users designing deep learning models processing non-vectorial structures and constraints.

As this is the first approximation theoretic result in this direction, there are naturally as many questions raised as have been answered. In particular, it is natural to ask: “Are the probabilistic trans_former networks trainable in practice; especially when K is non-convex?”. In Appendix 5, we show_
that the answer is indeed: “Yes!”, by proposing a training algorithm in that direction and showing
that we outperform an MLP model and a classical transformer network in terms of a joint MSE and
distance to the constraint set. The evaluation is performed on a large number of randomly generated
experiments, whose objective is to reduce the MSE to a randomly generated function mapping a
high-dimensional Euclidean space to there sphere R[3] with outputs constrained to the sphere.

1415FollowingExplicit constants are recorded in Table Afsari (2011), we make the convention that if 2 within the paper’s appendix; there, C  0 then, _p1C_ [is interpreted as] ✏K and ✏f may differ.[ 1][.]


-----

ACKNOWLEDGMENTS

Anastasis Kratsios and Ivan Dokmani´c were supported by the European Research Council (ERC)

Starting Grant 852821—SWING. The authors thank Wahid Khosrawi-Sardroudi, Phillip Casgrain,
and Hanna Sophia Wutte from ETH Z¨urich, Valentin Debarnot from the University of Basel for

their helpful feedback, and Sven Seuken from the University of Z¨urich for his helpful feedback in

the rebuttal phase.


REFERENCES

Bijan Afsari. Riemannian L[p] center of mass: existence, uniqueness, and convexity. Proceedings of

_the American Mathematical Society, 139(2):655–673, 2011._

Charalambos D. Aliprantis and Kim C. Border. Infinite dimensional analysis: A hitchhiker’s guide.

Springer, Berlin, third edition, 2006.

Luigi Ambrosio and Daniele Puglisi. Linear extension operators between spaces of Lipschitz maps

and optimal transport. Journal f¨ur die Reine und Angewandte Mathematik, 764:1–21, 2020.

[Anonymized. Pytorch implementation of attend-to-constraints, 2021. URL https://drive.](https://drive.google.com/file/d/1vryYsUmHt0fok3Mrje6oN9Tjs2UmpgkA/view)

[google.com/file/d/1vryYsUmHt0fok3Mrje6oN9Tjs2UmpgkA/view.](https://drive.google.com/file/d/1vryYsUmHt0fok3Mrje6oN9Tjs2UmpgkA/view)

Jean-Pierre Aubin and H´el`ene Frankowska. _Set-valued analysis._ Modern Birkh¨auser Classics.

Birkh¨auser Boston, Inc., Boston, MA, 2009.

Michel Baes, Calypso Herrera, Ariel Neufeld, and Pierre Ruyssen. Low-rank plus sparse decompo
sition of covariance matrices using neural network parametrization. IEEE Transaction on Neural
_Networks and Learning Systems, 2021._

Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly

learning to align and translate. In Proceedings of the International Conference on Learning Rep_resentations (ICLR), 2015._

Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the Thirtieth

_Annual ACM Symposium on the Theory of Computing, pp. 161–168. ACM, New York, 1999._

Basel Committee on Banking Supervision. Fundamental review of the trading book: outstanding

[issues, February 2015. https://www.bis.org/bcbs/publ/d305.pdf.](https://www.bis.org/bcbs/publ/d305.pdf)

Basel Committee on Banking Supervision. Minimum capital requirements for market risk, February

[2019. https://www.bis.org/bcbs/publ/d457.pdf.](https://www.bis.org/bcbs/publ/d457.pdf)

Heinz H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in

_Hilbert spaces. CMS Books in Mathematics/Ouvrages de Math´ematiques de la SMC. Springer,_

[New York, 2011. ISBN 978-1-4419-9466-0. doi: 10.1007/978-1-4419-9467-7. URL https:](https://doi.org/10.1007/978-1-4419-9467-7)
[//doi.org/10.1007/978-1-4419-9467-7. With a foreword by H´edy Attouch.](https://doi.org/10.1007/978-1-4419-9467-7)


Claude Berge. _Espaces Topologiques (Topological Spaces)[´]_ . Dunod, 1963.

Rabi Bhattacharya and Vic Patrangenaru. Large sample theory of intrinsic and extrinsic sample

means on manifolds. The Annals of Statistics, 31(1):1–29, 2003.

Silv`ere Bonnabel and Rodolphe Sepulchre. Riemannian metric and geometric mean for positive

semidefinite matrices of fixed rank. SIAM Journal on Matrix Analysis and Applications, 31(3):
1055–1070, 2009.

Silv`ere Bonnabel, Anne Collard, and Rodolphe Sepulchre. Rank-preserving geometric means of

positive semi-definite matrices. Linear Algebra and its Applications, 438(8):3202–3216, 2013.

Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet
ric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18–42,
2017.


-----

Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veliˇckovi´c. Geometric deep learn
[ing: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.08708, 2021. URL http:](http://arxiv.org/abs/2104.13478)
[//arxiv.org/abs/2104.13478.](http://arxiv.org/abs/2104.13478)

Bernard Bru, Henri Heinich, and Jean-Claude Lootgieter. Distances de L´evy et extensions des

th´eorem`es de la limite centrale et de Glivenko-Cantelli. Publ. Inst. Statist. Univ. Paris, 37(3-4):

29–42, 1993.

Alexander Brudnyi and Yuri Brudnyi. Methods of geometric analysis in extension and trace prob
_lems. Volume 1, volume 102 of Monographs in Mathematics. Birkh¨auser/Springer Basel AG,_

Basel, 2012a.

Alexander Brudnyi and Yuri Brudnyi. Methods of geometric analysis in extension and trace prob
_lems. Volume 2, volume 103 of Monographs in Mathematics. Birkh¨auser/Springer Basel AG,_

Basel, 2012b.

Elia Bru`e, Simone Di Marino, and Federico Stra. Linear Lipschitz and C [1] extension operators

through random projection. Journal of Functional Analysis, 280(4):108868, 2021.

Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. In

_Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2020._

Michele Conforti, G´erard Cornu´ejols, and Giacomo Zambelli. Integer Programming, volume 271

of Graduate Texts in Mathematics. Springer, Cham, 2014.

Christa Cuchiero, Lukas Gonon, Lyudmila Grigoryeva, Juan-Pablo Ortega, and Josef Teichmann.

Discrete-time signatures and randomness in reservoir computing. IEEE Transactions on Neural
_Networks and Learning Systems, pp. 1–10, 2021._

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Proceedings of

_Advances in Neural Information Processing Systems (NeurIPS), pp. 2292–2300, 2013._

George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con
_trol, Signals, and Systems, 2(4):303–314, 1989._

Meng Ding and Guoliang Fan. Multilayer joint gait-pose manifolds for human gait motion modeling.

_IEEE Transactions on Cybernetics, 45(11):2413–2424, 2014._

Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, and Martin Vetterli. Euclidean distance matrices:

Essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6):12–30,
2015. doi: 10.1109/MSP.2015.2398954.

Richard M. Dudley. Real analysis and probability, volume 74 of Cambridge Studies in Advanced

_Mathematics. Cambridge University Press, Cambridge, 2002._

Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network

function approximation in reinforcement learning. Neural Networks, 107:3–11, 2018.

Charles L. Fefferman. A sharp form of Whitney’s extension theorem. Annals of Mathematics, 161

(1):509–577, 2005.

Thomas Fletcher. Geodesic regression and the theory of least squares on Riemannian manifolds.

_International Journal of Computer Vision, 105(2):171–185, 2013._

Maurice Fr´echet. Les ´el´ements al´eatoires de nature quelconque dans un espace distanci´e. Annales

_de l’Institut Henri Poincar´e, 10:215–310, 1948._

Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pablo Ortega. Risk bounds for reservoir comput
[ing. Journal of Machine Learning Research, 21(240):1–61, 2020a. URL http://jmlr.org/](http://jmlr.org/papers/v21/19-902.html)
[papers/v21/19-902.html.](http://jmlr.org/papers/v21/19-902.html)

Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pablo Ortega. Approximation bounds for random

neural networks and reservoir systems. arXiv preprint arXiv:2002.05933, 2020b.


-----

Lyudmila Grigoryeva and Juan-Pablo Ortega. Universal discrete-time reservoir computers with

stochastic inputs and linear readouts using non-homogeneous state-affine systems. _J. Mach._

_Learn. Res., 19:Paper No. 24, 40, 2018._

Lyudmila Grigoryeva and Juan-Pablo Ortega. Differentiable reservoir computing. J. Mach. Learn.

_Res., 20:Paper No. 179, 62, 2019._

Ingo G¨uhring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep

ReLU neural networks in W _[s,p]_ norms. Analysis and Applications, 18(5):803–859, 2020.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing

human-level performance on ImageNet classification. In Proceedings of the IEEE international
_conference on computer vision, pp. 1026–1034, 2015._

Juha Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York,

2001.

Ludger Holters, Bj¨orn Bahl, Maike Hennen, and Andr´e Bardow. Playing Stackelberg games for

minimal cost for production and utilities. In ECOS 2018-Proceedings of the 31st International
_Conference on Efficiency, Cost, Optimisation, Simulation and Environmental Impact of Energy_
_Systems, pp. 36–36. University of Minho, 2018._

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni
versal approximators. Neural Network, 2(5):359–366, July 1989.

Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconcave

minimax optimization? In Proceedings of the International Conference on Machine Learning

_(ICML), 2020._

William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert

space. In Conference in modern analysis and probability, volume 26 of Contemp. Math., pp.
189–206. American Mathematical Society, RI, 1984.

J¨urgen Jost. Riemannian geometry and geometric analysis. Universitext. Springer, Heidelberg,

seventh edition, 2017.

Heinrich W. E. Jung. Uber die Cremonasche Transformation der Ebene.¨ _J. Reine Angew. Math.,_

138:255–318, 1910. ISSN 0075-4102. doi: 10.1515/crll.1910.138.255.

Olav Kallenberg. Foundations of modern probability, volume 99 of Probability Theory and Stochas
_tic Modelling. Springer, Cham, third edition, 2021._

Hermann Karcher. Riemannian center of mass and mollifier smoothing. Communications on Pure

_and Applied Mathematics, 30(5):509–541, 1977._

Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Jacob

Abernethy and Shivani Agarwal (eds.), Proceedings of Machine Learning Research, volume 125,
pp. 2306–2327. PMLR, 09–12 Jul 2020.

Achim Klenke. Probability theory: A comprehensive course. Universitext. Springer, London, sec
ond edition, 2014.

Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized

sliced Wasserstein distances. In Proceedings of Advances in Neural Information Processing Sys_tems (NeurIPS), 2019._

Anastasis Kratsios. Universal regular conditional distributions. arXiv preprint:2105.07743, 2021.

[URL https://arxiv.org/abs/2105.07743.](https://arxiv.org/abs/2105.07743)

Anastasis Kratsios and Eugene Bilokopytov. Non-Euclidean universal approximation. In Proceed
_ings of Advances in Neural Information Processing Systems (NeurIPS), 2020._

Anastasis Kratsios and Leonie Papon. Universal approximation theorems for differentiable geomet
[ric deep learning, 2021. URL https://arxiv.org/abs/2101.05390.](https://arxiv.org/abs/2101.05390)


-----

James R. Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Inven
_tiones Mathematicae, 160(1):59–95, 2005._

Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex
[strongly-concave min-max optimization. arXiv:2104.08708, 2021. URL https://arxiv.](https://arxiv.org/abs/2104.08708)
[org/abs/2104.08708.](https://arxiv.org/abs/2104.08708)

Yuanyuan Liu, Fanhua Shang, James Cheng, Hong Cheng, and Licheng Jiao. Accelerated first
order methods for geodesically convex optimization on riemannian manifolds. In Proceedings of
_Advances in Neural Information Processing Systems (NeurIPS), 2017._

Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa.

Differentiating through the Fr´echet mean. In Proceedings of the International Conference on

_Machine Learning (ICML), 2020._

Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks.

_Ann. Appl. Probab., 28(2):1190–1248, 2018. ISSN 1050-5164. doi: 10.1214/17-AAP1328. URL_
[https://doi.org/10.1214/17-AAP1328.](https://doi.org/10.1214/17-AAP1328)

Mantas Lukoˇseviˇcius and Herbert Jaeger. Reservoir computing approaches to recurrent neural net
work training. Computer Science Review, 3(3):127–149, 2009. ISSN 1574-0137.

Alexander J. McNeil, R¨udiger Frey, and Paul Embrechts. Quantitative Risk Management: Concepts,

_Techniques and Tools. Princeton Series in Finance. Princeton University Press, Princeton, NJ,_
2015.

Nina Miolane, Nicolas Guigui, Alice Le Brigant, Johan Mathe, Benjamin Hou, Yann Thanwerdas,

Stefan Heyder, Olivier Peltre, Niklas Koep, Hadi Zaatiti, Hatem Hajri, Yann Cabanes, Thomas
Gerald, Paul Chauchat, Christian Shewmake, Daniel Brooks, Bernhard Kainz, Claire Donnat,
Susan Holmes, and Xavier Pennec. Geomstats: A python package for riemannian geometry in
machine learning. Journal of Machine Learning Research, 21(223):1–9, 2020.

Theodore Samuel Motzkin. Sur quelques propri´et´es caract´eristiques des ensembles born´es non

_convexes. Bardi, 1935._

James R. Munkres. Topology. Prentice Hall, Inc., Upper Saddle River, NJ, 2000. Second edition.


Shin-ichi Ohta. Extending Lipschitz and H¨older maps between metric spaces. Positivity, 13(2):

407–425, 2009.

Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation.

_International Conference on Learning Representations (ICLR), 2021._

Ofir Pele and Michael Werman. Fast and robust Earth Mover’s distances. In Proceedings of the 12th

_IEEE International Conference on Computer Vision (ICCV), pp. 460–467, 2009._

Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural

networks and fully-connected networks. Proceedings of the American Mathematical Society, 148
(4):1567–1581, 2020.

Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 1999,

8:143–195, 1999.

Chayne Planiden and Xianfu Wang. Most convex functions have unique minimizers. Journal of

_Convex Analysis, 23(3):877–892, 2016._

Pakize Simin Pulat. On the relation of max-flow to min-cut for generalized networks. European

_Journal of Operational Research, 39(1):103–107, 1989._

Michael Puthawala, Konik Kothari, Matti Lassas, Ivan Dokmani´c, and Maarten de Hoop. Glob
[ally injective ReLU networks. arXiv:2006.08464, 2020. URL https://arxiv.org/abs/](https://arxiv.org/abs/2105.07743)
[2105.07743.](https://arxiv.org/abs/2105.07743)

Prajit Ramachandran, Barret Zoph, and Quoc Le. Searching for activation functions. In Proceedings

_of the International Conference of Learning Representations (ICLR), 2018._


-----

Alexander Robey, George J Pappas, and Hamed Hassani. Model-based domain generalization.

_[arXiv:2102.11436, 2021. URL https://arxiv.org/abs/2102.11436.](https://arxiv.org/abs/2102.11436)_

James C. Robinson. Dimensions, embeddings, and attractors, volume 186 of Cambridge Tracts in

_Mathematics. Cambridge University Press, Cambridge, 2011._

Denis Rosset, Felipe Montealegre-Mora, and Jean-Daniel Bancal. RepLAB: A computa
tional/numerical approach to representation theory. In Quantum Theory and Symmetries, pp.

643–653. Springer, 2021.

Shai Shalev-Shwartz and Shai Ben-David. _Understanding Machine Learning: From Theory to_

_Algorithms. Cambridge University Press, USA, 2014._

Zuowei Shen, Haizhao Yang, and Shijun Zhang. Neural network approximation: Three hidden

layers are enough. Neural Networks, 141:160–173, 2021a.

Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network with approximation error being

reciprocal of width to power of square root of depth. Neural Computation, 33(4):1005–1036, 03
2021b.

Max Sommerfeld, J¨orn Schrieber, Yoav Zemel, and Axel Munk. Optimal transport: Fast proba
bilistic approximation with exact solvers. Journal of Machine Learning Research, 20(105):1–23,
2019.

Karl-Theodor Sturm. Probability measures on metric spaces of nonpositive curvature. In Heat

_kernels and analysis on manifolds, graphs, and metric spaces, volume 338 of Contemp. Math.,_
pp. 357–390. Amer. Math. Soc., Providence, RI, 2003.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez,

Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of Advances
_in Neural Information Processing Systems, pp. 5998–6008, 2017._

C´edric Villani. Optimal Transport: Old and New, volume 338. Springer, 2009.


James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. On the regularity of attention.

_[arXiv:2102.05628, 2021. URL https://arxiv.org/abs/2102.05628.](https://arxiv.org/abs/2102.05628)_

Steven Weinberg. Implications of dynamical symmetry breaking. Physical Review D, 13(4):974,

1976.

Hassler Whitney. Analytic extensions of differentiable functions defined in closed sets. Transactions

_of the American Mathematical Society, 36(1):63–89, 1934._

Dmitry Yarotsky. Elementary superexpressive activations. In Proceedings of the 38th International

_Conference on Machine Learning (ICML), 2021._

Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural

networks. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS),
volume 33, 2020.

Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are

transformers universal approximators of sequence-to-sequence functions? In Proceedings of the
_International Conference on Learning Representations (ICLR), 2020a._

Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and

Sanjiv Kumar. O(n) connections are expressive enough: Universal approximability of sparse
transformers. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS),
2020b.

Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Pro
_ceedings of the 29th Conference on Learning Theory (COLT), 2016._

Ding-Xuan Zhou. Universality of deep convolutional neural networks. Applied and Computational

_Harmonic Analysis, 48(2):787–794, 2020._


-----

