Universal Approximation Theorem for Equivariant Maps by Group CNNs
Authors: Wataru Kumagai
Akiyoshi Sannai
Venue:  (2021)
Keywords: Universal Approximation Theorem
CNN
Deep Learning
Symmetry

Abstract: Group symmetry is inherent in a wide variety of data distributions. Data processing that preserves symmetry is described as an equivariant map and often effective in achieving high performance. Convolutional neural networks (CNNs) have been known as models with equivariance and shown to approximate equivariant maps for some specific groups. However, universal approximation theorems for CNNs have been separately derived with individual techniques according to each group and setting. This paper provides a unified method to obtain universal approximation theorems for equivariant maps by CNNs in various settings. As its significant advantage, we can handle non-linear equivariant maps between infinite-dimensional spaces for non-compact groups.

Under review as a conference paper at ICLR 2021
UNIVERSAL APPROXIMATION THEOREM FOR EQUIVARIANT MAPS BY GROUP CNNs
Anonymous authors Paper under double-blind review
ABSTRACT
Group symmetry is inherent in a wide variety of data distributions. Data pro- cessing that preserves symmetry described as an equivariant map and often effective in achieving high performance. Convolutional neural networks (CNNs) have been known as models with equivariance and shown to approximate equivari- ant maps for some specific groups. However, universal approximation theorems for CNNs have been separately derived with individual techniques according to each group and setting. This paper provides unified method to obtain univer- sal approximation theorems for equivariant maps by CNNs in various settings. handle non-linear equivariant maps between
As its significant advantage, -innte-dimeniionall spaces for non-compas groups.
INTRODUCTION
Deep neural networks have been widely used models to approximate underlying functions in various machine learning tasks. The expressive power of fully-connected deep neural networks was first mathematically guaranteed by the universal approximation theorem in Cybenko (1989), which states that any continuous function on a compact domain can be approximated with any precision by an appropriate neural network with sufficient width and depth. Beyond the classical result stated above, several types of variants of the universal approximation theorem have also been investigated under different conditions.
Among wide variety of deep neural networks, convolutional neural networks (CNNs) have achieved impressive performance for real applications. In particular, almost all of state-of-the-an models for image recognition are based on CNNs. These successes are closely related to the prop- erty that performing CNNs commute with translation on pixel coordinate. That is, CNNs can con- serve symmetry about translation in image data. In general, this kind of property for symmetry is known as the equivariance, which is a generalization of the invariance. When data distribution has some symmetry and the task to be solved relates the symmetry, data processing is desired to be equivariant on the symmetry. In recent years, different types of symmetry have been focused per each task, and has been proven that CNNs can approximate arbitrary equivariant data processing for specific symmetry. These results are mathematically captured as the universal approximation for equivariant maps and represent the theoretical validity of the use of CNNs.
In order to theoretically correctly handle symmetric structures, we have to carefully consider the structure of data space where data distributions are defined. For example, in image recognition tasks, image data are often supposed to have symmetry for translation. When each image data is acquired, there are finite pixels equipped with an image sensor, and an image data represented by a finite- dimensional vector in Euclidean space IR where d is the number of pixels. However, we note that the finiteness of pixels stems from the limit of the image sensor and a raw scene behind the image data is thought to be modelled by an element in S with continuous spatial coordinates S, where g a set of functions from S to R. Then, the element in S is regarded as a functional representation of the image data in Rd In this paper, in order to appropriately formulate data symmetry. treat both typical data representation in dinee-dimensional settings and functional representation in settings in unified manner.

---

Under review as a conference paper at ICLR 2021
1.1 RELATED WORKS
Symmetry and functional representation. Symmetry is mathematically described in terms of groups and has become an essential concept in machine learning. Gordon et al. (2019) point out that, when data symmetry is represented by infinite group like the translation group, equivari- ant maps, which are symmetry-preserye dimensional spaces but can be described by maps between infiniteddimensional function spaces. As a related study about of functional representations and investigate practical computational methods such as discretization and localization.
processing, cannot be captured as maps between finite-
processing, Finzi et al. (2020) propose group convolution
Universal approximation for continuous maps. The universal approximation theorem, which is the main objective of this paper, is one of the most classical mathematical theorems of neu- ral networks. The universal approximation theorem states that a feedforward fully-connected network (FNN) with a single hidden layer containing finite neurons can approximate contin- uous function on a compact subset of IRd. Cybenko (1989) proved this theorem for the sig- moid activation function. After his work, some researchers showed similar results to general- ize the sigmoidal function to a larger class of activation functions as Barron (1994), Hornik et al. (1989), Funahashi (1989), Kürková (1992) and Sonoda & Murata (2017). These results were ap- proximations to functional representations between finite-dimensional vector spaces, but recently Guss & Salakhutdinov (2019) generalized them continuous maps between infinite-dimensional function spaces in Guss & Salakhutdinov (2019).
Equivariant neural networks. The concept of group-invariant neural networks was first intro- duced in Shawe-Taylor (1989) in the case of permutation groups. In addition to the invariant case, Zaheer al. (2017a) designed group-equivarian neural networks for permutation groups and ob- tained excellent results in many applications. Maron et al. (2019a: 2020) consider and develop a theory of equivariant tensor networks for general finite groups. Petersen & Voigtlaender (2020) es- tablished connection between group CNNs, which are equivariant networks, and FNNs for group finites. However, symmetry are not limited to finite groups Convolutional neural networks (CNNs) was designed to be equivariant for translation groups and achieved impressive performance in wide variety of tasks. Gens & Domingos (2014) proposed architectures that are based on CNNs and invariant to more general groups including affine groups. Motivated by CNN's experimental success, many researchers have further generalized this by using group theory. Kondor & Trivedi (2018) proved that, when group is compact and the group action is transitive, a neural network constrained by some homogeneous structure is equivariant if and only if it becomes a group CNN.
Universal approximation for equivariant maps. Compared the vast studies about universal approximation for continuous maps, there are few existing studies about universal approximation for equivariant maps. Sannai et al. (2019); Ravanbakhsh (2020); Keriven & Peyré (2019) consid- ered the equivariant model for finite groups and proved universal approximation property of them by attributing to the results of Maron et al. (2019b). Cohen et al. (2019) considered group convo- lution on homogeneous space and proved that a linear equivariant map is always convolution- like. Yarotsky (2018) proved universal approximation theorems for nonlinear equivariant maps by CNN- like models when groups are the d-dimensional translation group T(d) Rd or the 2-dimensional Euclidean group SE2.). However, when groups are more general, universal approximation theorems for non-line monelrnear& equivariant maps have not been obtained.
1.2 PAPER ORGANIZATION AND OUR CONTRIBUTIONS
The paper is organized as follows. In section 2, we introduce the definition of group equivariant maps and provide the essential property that equivariant maps have one-to-one correspondence to theoretically tractable maps called generators. In section 3, we define fully-connected and group convolutional neural networks between function spaces. This formulation is suitable to represent data symmetry. Then, we provide a main theorem called the conversion theorem that can convert FNNs to CNNs. In section 4, using the conversion theorem, we derive universal approximation theorems for non-lineat equivariant maps by group CNNs. In particular, this is the first universal approximation theorem for equivariant maps in infinite groups are handled in a unified manner. In section 5, we provide concluding remarks and mention future works.
settings. We note that finite and
2

---

Under review as a conference paper at ICLR 2021
2
GROUP EQUIVARIANCE
2.1 PRELIMINARIES
We introduce definitions and terminology used in the later discussion.
Functional representation. In this paper, sets denoted by S, T and G are assumed to be locally a set, we denote by R$ the all maps from
compact, occompact, Hausdorff spaces. When S to I and by || oo the supremum norm. We call S of R$ the index set. We denote by C(S) the set of all continuous maps from S to R. We denote by Co(S) the set of continuous functions from S to I which vanish at infinity'. For Borel space S with some measure μ4, we denote the set of integrable functions from to with respect to μ as (S)) For subset C S, the restriction map Rg R$ + R is defined by RB(x) = z|g. where x E RS and r/s is the restriction of the domain of onto B.
When S is finite set, R$ is identified with the mniee-dimensionall Euclidean space $1 where [S] the cardinality of S. In this sense, IR for general sets a generalization of Euclidean spaces. However, R$ itself is often intractable for an infinite set S. In such cases, we instead consider C(S), Co(S) or (P)) as relatively tractable subspaces of I
Group action. We denote the identity element in group G by 1. We assume that the action of group G on a set
continuous. We denote by call G, {g- sig E G} the orbit of E S. From the definition, we have S = -Ues G.. When subset C
the left action of g E to S. Then we
the set of representative elements from all orbits, it satisfies the disjoint condition S LLeg G,. Then, call B base space? and define the projection Pg S - B by mapping 8 E S to the representative element in B n G.. When a group G acts on sets S and T, the action of
When group G acts a index set S. the G-translation operators Tg IRS + R for E G are defined by T, [x]x[(s) == x(g-t
G on the product space S x T is defined by g (s.t) (g-8,9 g.
where x E R and 8 E S. We often denote Ty [ar] simply by g a for brevity. Then, group translation determine the action of G on R.S.
2.2 GROUP EQUIVARIANT MAPS
In this section, introduce group equivariant maps and show their basic properties. First, we define group equivariance.
Definition 1 (Group Equivariance). Suppose that a group G acts on sets S and T. Then, a map F: R + R² is called G-equivariant when Flg- xx] = g F[x] holds for any G and E RS.
An example of an equivariant map in image processing is provided Figure 1.
To clarify the degree of freedom of equivariant maps, we define the generator of equivariant maps.
Definition 2 (Generator). Let B T be a base space with respect to the action of G on T. For G-equivariant map F: R - T we call FB == Rg the generator of F.
The following theorem shows that equivariant maps can be represented by their generators.
Theorem 3 (Degree of Freedom of Equivariant Maps). Let group G act on sets S and T, and C T a base space. Then, G-equivariant map F R -> TR. has one-to-one correspondence to its generator Fs.
detailed version of Theorem is proved in Section A.I.
A function ff on a locally compact space said to vanish infinity if, for any e, there exists a compact subset K. C S such that sup.esv:: [f())] <
"The choice
base space is not unique in general, However, the topological structure of base space
can he induced by the quotient space S/G.
We note that T Ty To' and the group translation operator is the action of G on R.S from the right.
3

---

Under review as a conference paper at ICLR 2021
S
Group Action
Equivariant Map
Equivariant Map
T
T
Group Action
F(æ)
g F(x
An example of an equivariant map from RGB images to gray-scale images. An RGB image x is represented by values (i.e., a function) on 2-dimensional spatial coordinates with RGB channels. This corresponds to the case where the index set is S = R2x3 R Similarly, gray-scale image F[x] after equivariant processing F; R$ + I is represented by values on 2- dimensional spatial coordinates with single gray-scale channel. This corresponds to the case where the index set is T = RR2.. In this figure, the group action is translation of G R22 to 2-dimensional spatial coordinates.
Figure 1:
FULLY-CONNECTED AND GROUP CONVOLUTIONAL NEURAL NETWORKS
3.1 FULLY-CONNECTED NEURAL NETWORKS
To define neural networks, we introduce some notions. A map A R$ + R called bounded affine map if there exist bounded linear map W R$ + RR and an element b E R² such that
A[z] = W [>] +
(1)
Guss & Salakhutdinov (2019) provide the following lemma, which is useful to handle bounded affine maps.
Lemma 4 (Integral Form, Guss & Salakhutdinov (2019)). Suppose that S and T are locally com- pact, a-compact, Hausdorff. measurable spaces. For bounded linear map W C(S) C(T), there exist Borel regular measure on S and weak" continuous family of functions (wit,-)) heeT C (S) such that the following holds for any C(S):
W(x](t) = [ ()((s))
To use the integral form, we assume in the following that the input and output spaces of the class of continuous maps C(S) and C(T) instead of IRS and R²,,, respectively. Using the integral form, a bounded affine map A is represented by
A (1) S (((s)))(()))(())) b(1)
In particular, when S and T are finite sets with cardinality d and d', the function spaces C(S) and C(T) identified with finite-dimensional Euclidean spaces R& and Rdd and thus, an affine map R - TR is parameterized by a weight matrix W [w](t,)) s))s(d))ee))))) Rdd RRd and bias vector 1 [bO))ej))) E IRd" and (2) induces the following form, which is often used in the literature on neural networks:
A[z](t) Σ w(t,s)x(s)) b(t).
(3)
4

---

Under review as a conference paper at ICLR 2021
A continuous function p: R + R induces the activation map ap C(S) - C(S) which is defined by ap(2) := p z E C(S) for x E C(S). However, for brevity, we denote ap by p. Then, we can define fully-connected neural networks in general settings.
Definition 5 (Fully-connected Neural Networks). Let E N. fully-connected neural network and an activation map p
with L layers is composition map of bounded affine maps represented by
: Ar, o po A
where Ar C(S ((E) are affine maps for some sequence of sets {St) Then, we denote by NPNN(p, L; St.) the set of all filly-connected neural networks from C(Sa) to C(Sr. with L layers and an activation function p.
We denote the measure of the affine map Ar in the first layer of fully-connected neural network by Hs. This measure Hs used describe condition in the main theorem (Theorem 9).
3.2 GROUP CONVOLUTIONAL NEURAL NETWORKS
We introduce the general form of group convolution.
Definition 6 (Group Convolution). Suppose that group G acts sets S and T. For G-invariant measure y/ on S, G-invariant functions v : $ x T + R and E C(T), the biased G-convolution Cu..b C(S) - C(T) is defined as
Cur,bla((t) := J vlt, ((t,)))(s)dvvl)) b(t).
(5)
In the right hand side, we call the first term the G-convolution and the second term the bias term.
In the following, we denote Cu..,b by C for brevity. When S and T are finite, we note that (5) also can be represented (3).
Definition includes existing definitions of group convolution follows. When S = T = G, the group G acts on S and T by left translations. Then, (5) without the bias term (i.e., = 0) is described as
Clx)(g) / v(g. ())(d)) 6(h ((())))x(())((1))
where 8(g) = v(g, 1). This is popular definition of group convolution between two functions G. Further, when S = x B and T G x (5) without the bias term is described as
[ 5(h g. s)x(h, (ddss))))))
Clzl(g,t) = JgB
v((g, T), ())()))((, sduu(())))
ggB
where ö(g, v((g.7) r). (1, s)). This coincides with the definition of group convolution in Finzi et al. (2020). We note that Finzi et al. (2020) also proposes discretization and localization of the above group convolution for implementation.
In conventional convolution used for image recognition, G represents spatial information such as pixel coordinate, and B' correspond to channels in consecutive layers é and L f+1 respectively, and v corresponds to a filter. In applications, the filter v is expected to have compact support or be short-tailed on G as in a allowed to be the Dirac delta or highly peaked around a single point in G, such convolution can be interpreted the x convolution.
convolution filter in discrete convolution. In particular, when
Then, we define group convolutional neural networks as follows.
Definition 7 (Group Convolutional Neural Networks). Let N. A G-convolational neural network with L layers is composition map of biased convolutions Ct C(Se-1) + C(S) (E L, l....,A. for some sequence of spaces {Be)== and an activation map with p as o Ci.
$ = Cr. po Cr.-1
(6)
Then, we denote by NCNN(G, p. L; Su, SL) the set of all G-convolutional neural networks from C(So) to C(S,,) with respect to group G with L layers and fixed activation function p.
A bivariate G-invariant function
G G R is determined by the univariate function 0 G
hecause v(g,h) - h) = r(h gg 1) 5(h-1g 9)
5

---

The conversion theorem be applied wide range of group actions. We explain the generality of the conversion theorem. First, sets S and T are not limited to finite sets or Euclidean spaces, and may be more general topological spaces. Second, a group G may be discrete (especially finite) or continuous groups. Moreover, G can be non-compact and non-commutative. Third, the action of group G' on sets S and T may not be transitive, and thus, the sets can be non-homogeneous spaces. In the following, we provide some concrete examples of group actions Under review as a conference paper at ICLR 2021
We easily verify the following proposition. Proposition 8. A G-convolutional neural network is G-equivariant.
In particular, each biased G-convolution Cv. G-equivariant. Conversely, Cohen al. (2019) showed that a G-equivariant linear map is represented by some G-convolution without the bias term when G locally compact and unimodular, and the action of a group is transitive (i.e., B consists of only single element).
3.3 CONVERSION THEOREM
In this section, we introduce the main theorem (Theorem 9), which is an essential part of obtaining universal approximation theorems for equivariant maps by group CNNs.
Theorem 9 (Conversion Theorem). Suppose that the action of a group G on sets S and T. We assume the following condition:
(CI) there exist base spaces Bs C S, BT C CT, and two subgroups Hy & Hs & such that S G/Hs x Bs and T G/HlT BT.
Further, suppose E' C Co(S) is compact and an FNN Φ : E' Co(BT) with Lipschitz activation function p satisfies
(C2) there exists a G-left-invariant locally finite measure v on S such that pa &
Then, for any c <> 0, there exists a CNN & + Co(T) with the activation number of layers of & equals that of & and
foncatiionnnccon function p such that the
|| - 00 S.
Moreover, for any G-equivariant map F Co(S) + Co(T), the following holds:
|| - 11 < |B l øllo +e.
(8)
We provide the proof of Theorem 9 in Section B.
Conversion Universal Approximation Theorems. The conversion theorem can convert uni- versal approximation theorem by FNNs to universal approximation theorem for equivariant maps by CNNs as follows. Suppose that the existence an FNN & which satisfies [[ Æ  S using some universal upproximation theorem by FNNs. Then, Theorem 9 guarantees the existence of a CNN which satisfies || E - Φ S 2e. other words, an FNN can approximate the generator of the target equivariant map on F,, then there exists CNN which approximates the whole of the equivariant map on E.
Applicable Cases.
when T and the actions of G S and TT are the same:
Symmetric Group. The action of G = Sn on S = [m] as permutation has the decomposi- tion [r]] = S,/Stta(()) x {*}. where Hs = Stab(1) is the set all permutations on [n] that fix 1 [ni] and Bs = {+} is singleton? Then, the counting measure can be taken as an invariant measure v.
The action of G O(d) on on S E {0} as rotation around 0 Rd has the decomposition Rd {0} = (dd)/O(d - 1) x R. The cases where G = SO(d) = 5 have similar decomposition. Then, the Lebesgue measure can be taken as an invariant measure v.
Rotation Group.
Hs and HT not assumed
normal subgroups.
"ig & means that Ne is absolutely continuous with respect to v.
A singleton is set with exactly element.

---

Under review as a conference paper at ICLR 2021
Translation Group.
The action of G R2 S R as translation has the trivial decomposition Fd = R /00 x {+}. Then, the Lebesgue measure can be taken as an
invariant measure v.
Euclidean Group. The action of G = E(d) on S = R as isometry has the decomposition I = ((d)/O(d) x {*). The case where G = SE(d) has a similar decomposition. Then, the Lebesgue measure can be taken as an invariant measure
Scaling Group. The action of G = I2 on S = I {0} as scalar multiplication has the decomposition Rd \ {0} / [1} S Then, the measure 14 X V54-1 can be taken as an invariant measure v, where the measure V4 on R>o is determined by u4 vra[a, 6)) == log and V/gu1 is a uniform measure on Sth-1
Lorentz Group. The action of G = SO* (d, 1), a subgroup of the Lorentz group O(d, 1), on the upper half plane* S = [H as matrix multiplication has the decomposition H|d+1 SO+(d, (d, ())5((n)) x {+]. Then, the F =+()) can be taken
left-invariant measure v, where w+ is a left-invariant measure on SOt (d, 1), SO (d, 1) - sot (d, (d,1)/SO(d) is a canonical projection, and क (v+) is the pushforward measure.
Inapplicable Cases. We explain some cases where the conversion theorem cannot be applied. First, similar to the above discussion, we consider the setting where S = T and the actions of G on S and are the same. We note that, even if actions of Gi and G2 on satisfy the conditions in the conversion theorem, common invariant measure for both 11 and G2 may not exist. Then, a group G including G1 and G2 as subgroups does not satisfies (C2). For example, there does Euclidean
not exist common invariant measure about the actions of translation and scaling space. In particular, the action of the general linear group GL,(d) on the Euclidean space does not have locally-finite left-invariant measure on Rd. Thus, the conversion theorem cannot applied the case. Next, as we saw above, our model can handle convolutions on permutation groups, but not on general finite groups. This depends on whether [n] can be represented by quotient of G, we will see later. This is also the case for tensor expressions of permutations, which require a different formulation.
Lastly, we consider the case where the actions of G on S and T differ. Here, S and T may and may not equal. As representative case, we consider the invariant case. When the stabilizer in T satisfies Hy = G. a G-equivariant map F Co(S) - Co(T) is said to be G-invariant. However, because of the condition 1lT & Hs in (CI), the conversion theorem cannot apply to the invariant case as long as Ils + G. This kind of restriction is similar to existing studies, where the invari- ant case is separately handled from the equivariant case (Keriven & Peyré (2019); Maehara & NT (2019); Sannai al. (2019)). In fact, we can show that the inequality (7) never hold for trivii invariant cases (i.e., Hs * G and H = G) as follows: From Hy = G, we have By = T and Rs, = id, and thus, (7) reduces to { 20| < e. Here, note that is an FNN, which is not invariant in general, and + is a CNN, which is invariant. Thus, & cannot approximate non-inve non-invariant within a small error e. This implies that (7) does not hold for small e. However, whether (8) holds for the invariant case is an open problem.
Remarks on Conditions (C1) and (C2). We consider the conditions (CI) and (C2).
In (CI), the subgroup Hs < G (resp. HT) represents the stabilizer group of the action of G on S (resp. T). Thus. (C1) requires that the stabilizer group on every point S (resp. T) is isomorphic to the common subgroup Hs (resp. HT). When the group action satisfies some moderate conditions, such a requirement known be satisfied for most points in the set. As a theoretical result, the principal orbit type theorem (cf. Theorem 1.32, Meinrenken (2003)) guarantees that, if the group action on a manifold S is proper and S/G connected, there exist a dense subset S' C S and a subgroup His C G called a principal stabilizer such that the stabilizer group on every point in S' is isomorphic to Hs.
Further, (C1) assumes that the sets S and T have the direct product form of some coset G/H and a base space B. Then, the case where the base space B consists of a single point is equivalent to the condition that the set is homogeneous. In this sense, (CI) can be regarded as relaxation of the homogeneous condition. In many practical cases, a set S on which G acts can be regarded as such direct product form. For example, when the action is transitive, the direct product decomposition "The upper half plane defined by Hd+1 = ([11....,,Tt E RR+1 | > 0}.
7

---

Under review as a conference paper at ICLR 2021
trivially holds with the base space that consists of single point. Even when the set S itself is not rigorously represented by the direct product form, removing some "small" subset W C S, the complement S N can be often represented by the direct form. For example, when G = O(d) acts on the set S = R as rotation around the origin A = (0), S W mentioned above. In applications, removing only the small subset. N is expected to be negligible.
V has a direct product form as
Next, we provide some remarks on the condition (C2). Let us consider two representative settings of set S. The first case is the setting where S is finite. When G-invariant measure has a positive value on every singleton in S, y satisfies (C2) for an arbitrary measure Mé on S. In particular, the counting measure on S is invariant and satisfies (C2). The second case is the setting where S is Euclidean space R. and He is the Lebesgue measure. Then, (C2) is satisfied with invariant measures on the Euclidean space for various group actions, including translation, rotation, scaling, and an Euclidean group.
Here, we give a general method to construet in (C2) for a compact-group action. When μé locally finite and continuous' with respect to the action of a compact group G. the measure v/ = VG* Me on S for a Haar measure Ve on G satisfies (C2), where (Vg * (A) := Lo (g).
4 UNIVERSAL APPROXIMATION THEOREMS FOR EQUIVARIANT MAPS
4.1 UNIVERSAL. APPROXIMATION THEOREM IN FINITE DIMENSION
We review the universal approximation theorem in dimee-diieesional settings. Cybenko (1989) derived the following seminal universal approximation theorem in dittessiinni settings.
Theorem 10 (Universal Approximation for Continuous Maps by FNNs, Cybenko (1989)). Let an activation function I R be non-constant, bounded and continuous. Let F Rd + Ø be continuous map. Then, for any compact E C Rd and e >> 0, there exists a two-layer fully connected neural network óg E NNNN((, (p, 2: [d], [d')) such that [ ΦEll <.
Since Co(S) Rlls for a finite set S, we obtain the following theorem by combining Theorem with Theorem 10.
Theorem 11 (Universal Approximation for Equivariant Continuous Maps by CNNs). Let an acti- vation function p R + I. be non-constant, bounded and Lipschitz continuous. Suppose that finite group G acts on finite sets S and T and (CI) in Thoerem 9 holds. Let F RIls - BIT be G-equivariant continuous map. For any compact set E Rels and e 0, there exists a two-layer convolutional neural network 4g E NNNNN 2; (). (T]) such that || | -glloo <.
We note that Petersen & Voigtlaender (2020) obtained a similar result to Theorem 11 in the case of finite groups.
Universality of DeepSets. DeepSets is known as invariant/equivariant models with sets as input and is known to have universality for invariant/equivariant functions set permutation (Zaheer al. (2017b); Ravanbakhsh (2020)). The equiariant model is a stack of affine transformations with W = AE +1 (1 is the all-one matrix) and bias b b=c (I,..., 1)" and then an activation function acted on. Here, we prove the universality of DeepSets as a corollary of Theorem 11. Firstly, we consider the equivariant model of DeepSets as the one we are dealing with by setting S G. H and B as follows. We set S = T = [n)], G = S,, H = Stab(1) == {s E S, s(1) = 1} and B = {=}, where (*) is a singleton. Then we can see that Stab(1) is subgroup G and its left cosets G/ = [n]. As a set, /ta/Stb is equal to [n), and the canonical Sa.action on Sn SntSttb((1) is equivalent to the permutation action on [n]. Therefore, C(G/E H x B) = C(nn) = R holds, and the equivariant model of our paper is equal to that of DeepSets.
Theorem 12. For any permutation equivariant function F RD - TRe", compact set F. C R and > there is an equivariant model of DeepSets (or equivalently, our model) &g E. - R such that [()) (l <
The proof of Theorem 12 is provided in Section C.
A measure Me is said to he continuous with respect to the action of group G if palg A) is continuous with respect g E G for all Borel set S.
8

---

Under review as a conference paper at ICLR 2021
4.2 UNIVERSAL APPROXIMATION THEOREM IN INFINITE DIMENSION
Guss & Salakhutdinov (2019) derived a universal approximation theorem for contimuous maps by FNNs in infinite-dimensional settings. However, the universal approximation theorem in Guss & Salakhutdinov (2019) assumed that the index set S in the input layer and TT in the out- put layer are compact. Combining the conversion theorem with it, we can derive corresponding universal approximation theorem for equivariant maps with respect to compact groups. However, the compactness condition for S and T is a crucial shortcoming to handle the action of non-compact groups such as translation or scaling. In order to overcome the above obstacle, we can show a novel universal approximation theorem for Lipschitz maps by FNNs as follows.
Theorem 13 (Universal Approximation for Lipschitz Maps by FNNs). Let activation functiin
P : R + IR be continuous and non-polynomial. Let S C I& and T Rdd' be domains. Let F: Co(S) + Co(T) be a Lipschitz map. Then, for any compact E C Co(S) and e > 0, there exist N and a two-layer fully connected neural network OE
A2 o po A1 E NNNN 2; (.S. such that A+H [+ + 6(2) E + C[V[[ = RR,, A2l W + 6(2) IR CC(T), Pég is the Lebesgue measure, and Fl 0Elx <c
We provide proof of Theorem 13 in the appendix. We note that S C Rd and T Red in Theorem 13 are allowed to be non-compact unlike the result in Guss & Salakhutdinov (2019). Combining Theorem 9 with Theorem 13, we obtain the following theorem.
Theorem 14 (Universal Approximation for Equivariant Lipschitz Maps by CNNs). Let an activation function p : R + IR be Lipschitz continuous and non pol-polyn..ial. Suppose that a group G acts on C I2d and T C Rdd and (C1) and (C2) in Thoerem 9 hold for the Lebesgue measure Pag- Let F Cu(S)
CT(T) be G-equivariant Lipschitz map. Then, for any compact set E C Co(S)) and é > 0, there exists a two-layer convolutional neural network Dg E ENCNN(P, S, such that ||F| F 11 <.
Lastly, we mention some universal approximation theorems for some concrete groups When a group G an Euclidean group E(d) or a special Euclidean group SE(d). Theorem 14 shows that group CNNs are universal approximators of G-equivariant maps. Although Yarotsky (2018) showed that group CNNs can approximate (2queeaquivaiian maps, our result for d 2 3 was not shown in existing studies. Since Euclidean groups can be used to represent 3D motion and point cloud, Theorem 14 can provide the theoretical guarantee of 3D data processing with group CNNs. As another example, when a group G is SO (d, 1), G acts the upper half plane Hd+1, which is shown to be suitable for word representations in NLP (Nickel & Kiela (2017)). Since the action of G preserves the distance Hd+ group convolution with SO + (d. 1) may be useful for NLP.
5 CONCLUSION
We have considered universal approximation theorems for equivariant maps by group CNNs. To prove the theorems, we showed that an equivariant map is uniquely determined by its generator. Thus, when we can take fully-connected neural network approximate the generator, the approx- imator of the equivariant map can be described as a group CNN from the conversion theorem. In this way, the universal approximation for equivariant maps by group CNNs can be obtained through the universal approximation for the generator by FNNs. We have described FNNs and group CNNs in an abstract way. In particular, we provided novel universal approximation theorem by FNNs in the infinite dimension, where the support of the input functions is unbounded. Using this result, we obtained the universal approximation theorem for equivariant maps for non-compact groups.
We mention future work. In Theorem 14, we assumed sets S and T to be subspaces of Euclidean spaces. However, in the conversion theorem (Theorem 9), sets S and do not need to be subspaces of Euclidean spaces and may have a more general topological structure. Thus, if there is a universal approximation theorem in non-Euclidean spaces (Courrieu (2005); Kratsios (2019)), we may be able to combine it with the conversion theorem and derive its equivariant version. Next, note the problem of computational complexity. Although group convolution can be implemented by, e.g., discretization and localization as in Finzi et al. (2020), such implementation cannot be applied to high- nigh-dimensional groups due to high computational cost. To use group CNNs for actual machine- learning problems, it is required to construct effective architecture for practical implementation.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-133, 1994.
Taco Cohen, Mario Geiger, and Maurice Weiler. general theory of equivariant enns on homo- geneous spaces. In Advances in Neural Information Processing Systems, pp. 9142-9153, 2019.
Pierre Courrieu. Function approximation non-euclidean spaces. Neural Networks, 18(1)911-102 2005.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303 -14, 1989.
Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolu- tional neural networks for equivariance to lie groups on arbitrary continuous data. arXiv preprint arXiv:2002.12880, 2020.
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 2(3): 183-192, 1989.
Robert Gens and Pedro M Domingos. Deep symmetry networks. In Advances in Neural Information Processing Systems, pp. 2537-2545, 2014.
Jonathan Gordon, Wessel P Bruinsma, Andrew YK Foong, James Requeima, Yann Dubois, and Richard E Turner. Convolutional conditional neural processes. arXiv preprint 13555669 2019.
William H Guss and Ruslan Salakhutdinov. On universal approximation by neural networks with uniform guarantees approximation of infinite dimensional maps. arXiv preprint arXiv: 545, 2019.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366, 1989.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, pp. 7092-7101,
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. arXiv preprini arXiv:/802.03690, 2018.
Anastasis Kratsios. The universal approximation property: Characterizations, existence, and canonical topology for deep-learning. arXiv preprint 1rXiv:19100033344.00 2019.
Mateusz Krukowski. peeche-kklmoogooo--ressz-
theorem on locally compact groups via arzela-ascoli's 's theorem. arXiv preprint /80100189 2018.
Vvera Kürková. Kolmogorov' theorem and multilayer neural networks. Neural networks, 5(3): 501-506, 1992.
Takanori Machara and Hoang NT. A simple proof the universality of invariant/equivariant graph neural networks. arXiv preprint 10000:191, 2019.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivari- ant graph networks. In International Conference on Learning Representations, 2019a. URL https: http:///ppeeeeiieeeee net. / forum?id=Syxa jc9tm..
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Proceedings of the 36th International Conference Machine Learning, 97, 2019b.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. arXiv preprint arXiv:2002.08599 2020.
Eckhard Meinrenken. Group actions on manifolds, Lecture Notes, University of Toronto, Spring, 2003, 2003.
10

---

Under review as a conference paper at ICLR 2021
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in neural information processing systems, pp. 6338 6347, 2017.
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.
Siamak Ravanbakhsh. MiXiv:2002.02912, 2020.
Universal equivariant
multilayer
perceptrons.
arXiv preprint
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation Invariant/equivariant functions by deep neural networks. arXiv preprint arXiv: arXiv:1903.01939 2019.
John Shawe-Taylor. Building symmetries into feedforward networks. In 1989 First IEE Interna- tional Conference on Artificial Neural Networks,(oom) Publ. No. 313), pp. 158-162. IET, 1989.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-266, 2017.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arXiv preprint arXiv:1804. 10306, 2018. URL:
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pp. 339 3391-3401, 2017a.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391- 3401, 2017b.


Reviews:
[{"review_id": "zk9i62blat2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a certain generalization of convolutional neural networks and equivariant linear networks to the infinite dimensional case, while covering also the discrete case, and offers a universality result. In more detail, the paper first characterizes  equivariant maps as the unique  extensions of \"generator\", namely regular maps that provide target functions (or vector) defined over a basic domain. In other words, any map that takes functions (or vectors) into functions (or vectors) defined over the representatives from the symmetry's equivalent classes can be extended uniquely to an equivariant map by enlarging its target domain according to the equivariance rule. Second, infinite dimensional fully connected networks (FNNs) and general (equivariant) convolution neural networks (CNNs) are described. The main result of the paper is the Conversion Theorem (Theorem 11), and its consequences. The theorem specify the conditions under which an FNN can be approximated by a CNN. Since FNNs are known to be universal this implies universality of CNNs.  \n\nI think the general CNN formulation and the Conversion theorem are of merit but i think the paper should undergo a rather serious revision before ready for publication. The main issues (that are detailed below) are: the paper does not sufficiently relate the discussed model or the universality results to previous or concrete models (set and graph NN, equivariant group NN, other unused but potentially useful variations), it does not provide sufficient explanation and justification to the different conditions in Theorem 11, there are some details in the proof and the description of Theorem 11 which are missing/unclear, Theorem 16 has some unclarity. I think attending these will provide a much more accessible and useful paper for the community.\n\nDETAILS.\n\n> Relations to previous work. The paper discuss a rather broad generalization of equivariant network (equations 4 and 5). I think exploring the relations to existing generalization to convolution neural networks and equivariant networks is in order. For example, when taking $\\mathcal{S}=\\mathcal{T}=[n]$ ($[n]=\\{1,2,...,n\\}$) and $G=S_n$ (the permutations of $[n]$) equation (4) seems to boil  down to  Deepsets of Zaheer et al. mapping $\\mathbb{R}^n\\rightarrow \\mathbb{R}^n$ equivariantly. Does theorem 1 implies that Deepsets (as equivariant model) is universal (as was proved in several previous works)? In this case, Theorem 3 states that any function $f_1(x)$ can be extended to be equivariant via $f_j(x)=f_1(g\\cdot x)$, where $g$ is a permutation such that $g(j)=1$. If this is all required for universality proof this would be a great simplification over previous proofs. This example could help the reader grasp this extension and also relate to previous works on equivariant learning.  What can be said about the equivariant tensor models and graph neural networks using the universality result in this paper? What can be said about the negative results of universality of second order (or higher order) tensor graph networks? Does the method in this paper imply group convolution networks are universal?  Are there any instantiations of the CNN discussed in this paper that are useful although not discussed in previous work? In summary, how the results in this paper relates to known and unknown results of CNN generalizations and what universality proof does it generalize? \n\n> Theorem 11. First, looking at the proof, I feel there is a condition of the FNN $\\phi$ that is missing from the theorem's formulation. That is, that the different layers of $\\phi$ should be mapping to and from functions on base domains of $G$, $\\mathcal{C}(\\mathcal{B})$. Without it I can't see how the extension to equivariant maps work. How is it guaranteed that $\\phi$ can be extended if internal states are defined on non-base domains? If this is true then how the FNN found from the universality result of FNN (e.g., Theorem 12 and 14) are guaranteed to satisfy this condition? Related to that, I couldn't exactly understand the claim of the second to last layers in the proof of Theorem 11: the first layer outputs a function in $\\mathcal{C}(G/H_\\mathcal{T}\\times \\mathcal{B})$, but the second layer of the FNN maps functions from some different domain $\\mathcal{C}(\\mathcal{B}_2)$. If I understand correctly, the idea of the proof is basically using the extension mechanism of Theorem 3 to extend mapping to functions over base domains to equivariant mappings. This seems to produce a sort of lift in the domain of the target function at every step. Is that correct? Can you provide the proof for a simple example of equivariant networks such as Deepsets? Minor: there are some wrongs equation references in the proof of Theorem 11.\n\n> The condition (C1) in Theorem is not clear to this reviewer. I think some examples and explanation should be provided. I could not really figure out, despite the following paragraphs, in what situations can we verify this condition and in what sense it limits the scope of the theorem. Is there a simple intuition or a way to check such subgroups exists? Are these normal subgroups?  Should $H_\\mathcal{T}$ be a strict subgroup of $F_{\\mathcal{S}}$? Is this condition holds in standard cases such as $[n]$ and $G=S_n$, or images and $90$ degrees rotations? Does it mean $\\mathcal{S}$ has to have a group structure? \n\n\n> In Theorem 16: How  do we make sure the first layer can be seen as a generator? Can we given $[N]$ the required base structure? Is $[N]$ a base domain of $G$ necessarily? This also relates to the question I asked above about the condition in Theorem 11. Anyway, this proof should be provided in the paper or supplamentary. \n\n> The authors mention that the invariant case cannot be handled. However, invariant functions can be made equivariant by considering the trivial representation, e.g., in the discrete case let $f(x)$ be invariant to $S_n$, then $f_i(x)= f(x)$ for all $i\\in [n]$ is equivariant I believe. Can we approximate this equivariant function? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kxROIr6WRkv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After discussions:\nI read the author's response and other reviews. The authors made a considerable effort to address my concerns. As a result, the paper has improved and I increased my score. \n\nHaving said that, I am still not sure that the paper is ready for publication in its current form. My main concern is still the accessibility/readability of the results in this paper, which I think can be further improved for the benefit of both the community and the authors (more accessible paper => more imapct). To conclude, the results in this paper are interesting and are strong enough to warrant a publication, but the paper can really benefit from another revision.\n \nSummary:\n\nThe paper studies the approximation power of equivariant neural networks in a very general setup: the input space is assumed to be a function space (compared to a finite-dimensional space in standard setups) and the group is assumed to be any locally compact group. The main theorem shows how to convert fully connected networks to equivariant networks. This is then used to derive universal approximation theorems from the well-known results on fully connected networks. The paper seems to suggest an interesting approach and the results seem significant but the paper is very hard to follow and I am not sure I understood it. See the comments below.\n\nStrong points:\n\nImportant problem - invariant/equivariant models provide a very helpful inductive bias for many tasks on symmetric inputs. Understanding their approximation power is crucial.\nThe idea of the main theorem, i.e. converting and FNN to CNN is new and might be useful.\n\n\nWeak points:\n\nThe paper is written badly and is very hard to follow. (1) the intro does not give enough information about what is actually done in the paper. The first time you see the contributions are in a short list at the end of the section. It is very hard to understand them this way. (2) Section 2.2 is unnecessarily overcomplicated and difficult to read, partially due to excessive notation. I think that the basic idea of this subsection can be written in a much simpler way. Discussing the invariant case might also help. I would also suggest rewriting the paper in the following way: start with S,T finite and present all the results. Then discuss the generalization to infinite S,T (which are less useful in my opinion).\nGeneral comment: *Please add examples* - this will help the reader follow the paper. Perhaps choosing a particular case of S,T an G and exemplifying any result in the paper on this setup can be useful.\nRelation to prior work is not discussed. What is the relation of theorem 13 to the results obtained by Maron, Keriven and Ravanbakhsh? Specifically, these works show that in some cases high order tensors are needed for universal approximation by invariant neural networks - can this result be recovered from your results?\n\nRecommendation: \n\nThe results in this paper seem strong and important, but in its current form it cannot be accepted. I recommend a significant revision of the paper to make it more readable. I would be happy to increase my score (and confidence) in this case.\n\n\nMinor comments:\n\nThere are many typos in the paper. \nP. 2 - replace subrepresentation with subgroup?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "R4hVaLHE2Yq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proves a universal approximation theorem for equivariant maps by group convolutional networks in an extremely general setting. The proof applies to discrete and continuous settings, including infinite dimensional ones. \n\nThe general idea of the proof is as follows. First, it is shown that an equivariant map is determined by its generator, i.e. its values on the orbits (so far, not surprising). This means that one only has to prove universality for the generator. Universality is then proved for the generator by a fully connected network, and separately an approximation theorem of FCNs by CNNs is proved.\n\nProving a result of this generality is technically very challenging. Although I am not a professional mathematician, I know that there are many pitfalls when proving results like the one in this paper. For instance, the orbit space can be topologically very complicated. Having spent about a day with this paper, I think that at least the general idea of the proof is sound, and the authors have sidestepped several technical problems I could think of using well chosen technical assumptions. My knowledge of topology and analysis is not sufficient to fully vouch for the technical correctness in every detail though.\n\nUniversal approximation theorems are considered to be an important kind of result, and this paper proves a very general one for equivariant maps. Provided the other reviewers do not surface any technical concerns I would recommend acceptance.\n\n\nTypos and minor issues:\n- \"AAmong\"\n\n- I would recommend not putting a numbered footnote at the end of an equation, as it could be read as a power. E.g. mu_phi << nu^5. Better to put the footnote after the last English word or something like that. \n\n- On condition C1: if H_S represents the stabilizer subgroup and this group is the same at all points, then it seems to me the condition is similar to assuming that S is a homogeneous space for G, as has often been done in previous work. Would it be possible to just make that assumption?\n\n----\nUpdate:\nI do agree with the other reviewers that the paper may be difficult to read, especially for non experts. Nevertheless I still think the paper makes a nice contribution, so I will keep my rating.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the question of universal approximation with neural networks under general symmetries. For this purpose, the authors first leverage existing universal approximation results with shallow fully connected networks defined on infinite-dimensional input spaces, that are then upgraded to provide Universal Approximation of group-equivariant functions using group equivariant  convolutional networks. 

Reviewers were all appreciative of the scope of this paper, aimed at unifying different UAT results under the same underlying 'master theorem', bringing a much more general perspective on the problem of learning under symmetry. However, reviewers also expressed concerns about the accessibility and readibility of the current manuscript, pointing at the lack of examples and connections with existing models/results. Authors did a commendable job at adding these examples and incorporating reviewers feedback into a much improved revision. 

After taking all the feedback into account, this AC has the uncomfortable job of recommending rejection at this time. Ultimately, the reason is that this AC is convinced that this paper can be made even better by doing an extra revision that helps the reader navigate through the levels of generality. As it turns out, this paper was reviewed by three top senior experts at the interface of ML and groups/invariances, who themselves found that the treatment could be made more accessible --- thus hinting a difficult read for non-experts. In particular, the main result of this work (theorem 9) is based on a rather intuitive idea (that one can leverage UAT for generic neural nets on the generator of an equivariant function), that requires some technical 'care' in order to be fleshed out. The essence of the proof can be conveyed in simple terms, after which following through the proof is much easier. Similarly, the paper quickly adopts an abstract (yet precise) formalism in terms of infinite-dimensional domains, which again clouds the essential ideas in technical details. While the paper now contains several examples, this AC believes the authors can go to the extra mile of connecting them together, and further discussing the shortcomings of the result --- in particular, the remarks on tensor representations and the invariant case are of great importance in practice, and should be discussed more prominently. Finally, while this work is only concerned with universal approximation, an important aspect that is not mentioned here is the quantitative counterpart, ie what are the approximation rates for symmetric functions under the considered models.  

Decision: Reject