Universal approximations of permutation invariant/equivariant functions by deep neural networks
Authors: Akiyoshi Sannai
Yuuki Takai
Matthieu Cordonnier
Venue:  (2020)
Keywords: finite group
invariant
equivariant
neural networks

Abstract: In this paper, we develop a theory about the relationship between $G$-invariant/equivariant functions and deep neural networks for finite group $G$. Especially, for a given $G$-invariant/equivariant function, we construct its universal approximator by deep neural network whose layers equip $G$-actions and each affine transformations are $G$-equivariant/invariant. Due to representation theory, we can show that this approximator has exponentially fewer free parameters than usual models. 

Under review as a conference paper at ICLR 2020
UNIVERSAL APPROXIMATIONS OF PERMUTATION IN- VARIANT/EQUIVARIANT FUNCTIONS BY DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we develop theory about the relationship between G- invarian//eqiivariant functions and deep neural networks for finite group G. Es- pecially, for given G-invariant/equivariant function, we construct its universal approximator by deep neural network whose layers equip G-actions and each affine transformations are G-equivvriant//vaaian Due to representation theory, we can show that this approximator has far fewer free parameters than usual models.
INTRODUCTION
Deep neural networks have great success many applications such as image recognition, speech recognition, natural language process and others as Alex et al. (2012). Goodfellow et al. (2013), Wan ctt al. (2013), and Silver et al. (2017). A common strategy in their works is to construct larger and deeper networks. However, one of the main obstructions about using very deep and large networks for learning tasks the so-called curse of dimensionalltyy Namely, the parameters' dimension increase, so does the required sample size. Then, the computational complexity becomes higher. An idea to overcome this is to design models with respect to the objective structure.
Zaheer al. (0117) designed model adapted machine learning tasks defined sets, which are, from a mathematical point of view, permutation invariant or equivariant tasks. They demonstrate surprisingly good applicability on their method on population statistic estimation, point cloud classification, set expansion, and outliers detection. Empirically speaking, their results are really significant. Many researchers studied invariant/equivarian networks as Qi al. (2017), Hartford et al. (2018). Risi Kondor (2018), Maron et al. (2019a), BBoemmReddy & Teh (2019), Kondor & Trivedi (2018). and so on. Nevertheless, theoretical guarantee their methods is not sufficiently considered. One of our motivations is to establish theoretical guarantee. In this paper, prove an invarian//qquivrrian version of the universal approximation theorem by constructing an approximator. For the symmetric group, approximator is close to the equivariant model of Zaheer et al. (2017) in a sense (see a remark after Theorem 2.2 We can calculate the number of the free parameters appearing in invariant/equivarian model, and show that this number is far fewer than one of the usual models.
For usual deep neural networks, universal approximation theorem was first proved by Cybenko (189).. It states that, when the width goes to infinity, (usual) neural network with single hidden layer can, with arbitrary accuracy, approximate any continuous function with compact support. Though his theorem was only for sigmoid activation functions, there are further versions of this theorem which allows some wider classes of activation functions. In the recent literature, the most commonly used activation function is the ReLU (Rectified Linear Unit) function, which is the one we focus on in this paper. Some important previous works on universal approximation theorem for ReLU activation function are by Barroo| ( (1994), Hornik et al. (1989), Funahashi (1989). Kūrková & Sanguineti (2002), and Sonoda Murata (017)). In particular, for part of the proof of our main theorem, we borrow the results of Sonoda & Murata (2017) and Hanin & Sellke (2017). The interest of the universal approximation theorem in learning theory is to guarantee that we can search in the space which contains the solutions. The universal approximation theorem states the existence of the model which approximates the target function in arbitrary accuracy. This means that if we use the suitable algorithm, we have the desired solutions. We cannot guarantee such situations

---

Under review as a conference paper at ICLR 2020
without the universal approximation theorem. Our universal approximation theorem allows to apply representation theory. By this point of view, we can calculate the number of free parameters of our approximator.
In the equivariant case, an essential key point of the proof is the one to one correspondence between G-equivariant functions and Stabe (i) (iviivarri functions. Here, G' is finite group and Staba is the subgroup of consisting of the elements which fix i. We first confirm this correspondence at the function level. After that, we rephrase by deep neural networks. This correspondence enables to reduce the equivariant case to the invariant case.
The invariant case has already established by some researchers Zaheer al. (2017 7) Yarotsky (2018)
Maron et al. (2019b). For G = Sn, here S is the symmetric group of degree n. Zaheer et al. (2017) showed that a representation theorem of S,, -sniivaria function which is famous Hilbert's s 13th problem by Kolmogorov (1956) and Arnold (957)) gives us explicit description. Due this theorem and the usual universal approximation theorem, we can construct concrete deep neural network of the invariant model. Recently, |aron al. (2019b) proved an invariant version of the universal approximation theorem for any finite group G using tensor structures. We borrow their results to obtain our main results.
solution for the
1.1 CONTRIBUTIONS
Our contributions are summarized follows:
We prove an invariant/equivariant version of the approximation theorems, which is a one step to understand the behavior of deep neural networks with permutations more generally group actions.
Using representation theory, we calculate the number of free parameters appearing in our models. As result, the number of parameter in models is far fewer than the one of the usual models. This means that our models are easier to train than the usual models.
Although our model is slightly different from the equivariant model of Zaheer et al. (2017) for G = Sn, our theorem guarantees that our model for finite group G can approximate any G- invariant/equivariant functions.
1.2 RELATED WORKS
Group theory, or symmetry an important concept in mathematics, physics, and machine learning. In machine learning, deep symmetry networks (symnets) is designed by Gens & Domingos (2014)
as a generalization of convnets that forms feature maps over arbitrary symmetry groups. Group equivariant Convolutional Neural Networks (G-CNNs) is designed by Cohen & Welling (2016), as natural generalization of convolutional neural networks that reduces sample complexity by exploiting symmetries. The models for permutation invarianteeqiivarian tasks are designed by Zaheer et al. (2017) to give great results on population statistic estimation, point cloud classification, set expansion, and outlier detection.
The universal approximation theorem is one of the most classical mathematical theorems of neural networks. As we saw in the introduction, Cybenko (1989) proved this theorem in 1989 for sigmoid activation functions. After his achievement, some researchers showed similar results to generalize
introduction,_yyeeko)
the sigmoid function a larger class of activation functions as Barron (1994), Homnk al. (9899)
Funahashi 1989). Kūrková (1992) and Sonoda & Murata (2017).
As mentioned above, the invariant case has been established. For G Sn Zaheer al. (2017)
essentially proved an invariant version of an universal approximation theorem. Yarotsky| (2018 gave a more explicit S, -,,iinvariant approximator by a shallow deep neural network. Maron et al. (2019b) considered a G-invariant model with some tensor structures for any finite group G. An equivariant version for finite group by shallow (hyper-)graph neural networks is proved by Keriven & Peyre (2019). Our architecture of approximator is different from theirs. Moreover, although they proved only for "squashing functions" which exclude ReLU functions, our theorem allows us to use the ReLU functions. We also remark that our setting in this paper is quite general. In particular, include tensor structures, hence graph neural networks. It must be interesting to compare the numbers of free parameters of models of us and Keriven & Peyré 20019)
2

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES AND MAIN RESULTS
In this paper, we treat fully connected deep neural networks. We mainly consider ReI. activation functions. Here, the ReLU activation function is defined by
ReLU(z) = max (0)
We remark that our argument during this paper works for any activation functions which satisfy usual universal approximation theorem. A deep neural network is built by stacking the blocks which consist of linear map and ReLU activation. More formally, it is function Zg from IR4, to IR R44+
defined by Z: (x) = (eL + b,), where W; E Rd xd; b, E Rd++1 In this case, de is called the width of the i-th layer. The output of the deep neural networks
((=)= = ZF o Z Z22 Z1 (a))
(1)
where H called the depth of the deep neural network. We define the width of a deep neural network as the maximum of the widths of all layers.
Our main objects are deep neural networks which are invariant/equivariant with actions by a finite group G. We review some facts about groups and these actions here. Some more details are written
in Appendix A Let S,, be the group consisting of permutations of n elements {1, 2..................... n). This S., is called the symmetric group of degree n. The symmetric group S,, acts on {1, 2, .., n. } by the permutation i + o o for a E S,,. By Proposition A. that any finite group G can be regarded as a subgroup of S., for positive integer n. Then, G also acts on {1, {I,...,0 n by the action as an element of S,. For i E {1, 2, .2,....11, nt), we define the orbit of i as O; G(i) = (a(i) E G). Then, the set {1.2..... n can be divided to a disjoint union of the orbits: (1.2......) n DJー O.,-
Let G be a finite group action on (1. Staba of G associated with x by the subgroup of elements of G fixing i. Then, by Proposition A.2 the orbit O and the set of cosets G G/Staba (i) are bijective. When G Sn. X = 2 n.).
.n.. For ..2..... n. we define the stabilizer subgroup
and x = 1, we set Stab, (1) = Stab(1) == Stabe (2).
We next consider an action of S,, on the vector space R., The left action " of S, on R. is defined by
T a (I1, _nn] = (20) (m))
for a E S,, and x = (#). vT) E RR. We also call this the permutation action of Sn on RR.. there is an injective group homomorphism y:: G + Sn. G acts on RD by the permutation action as an element of Sn by yp: For a E G and x E IR," we define a x = p(o) x. Then, we simply say that G acts on IR
Example 2.1. The finite group G = S2 is embedded into S₃ by y: (12) + (1.)., where (i is transposition between and j. In this case, the orbit decomposition of [1, 2, is (1, U (3). By this embedding an Sz-action on IR is defined: (p((1 2)) (x), 22, x3) = (12,
Example 2.2 (Tensors). The group action of G which is a subgroup of S, on tensors as in Maron al. (2019b) is realized as follows: An Sn-action on Rn xa is defined by the following injective homomorphism :p: G + Sanv: We fix a bijection from (1..... an*) to [I...... x (1,2,.... a}. and for E Sn. ((() E Sant defined by
for (iI....,ih) E m.k and j E aI.. ((k).
p(()) (iI,... (a.....,,..)) = (o-
Then, for a tensor X
(Ii in #1..... j=1,2..... E IR" xa a E Sn acts on RBnxa xa by p(o) X (Eo ( This action is same as one of Maron et al. (2019b).
Example 2.3 (n-tuple of D-dimensional vectors). We identify {,, ...,, [D] with {(i,]) | =
1. 1...., j = 1,......1 D) and define pp: S, > SAD as (i.)) = (o (a-1(1), ((), Let (I1,..., Fnn (RP)" be an n-tuple of D-dimensional vectors. Then, for o E S., o(o) (II,..... Inn)
(1) (.)))))). This means permutation of n vectors.
Definition 2.1. Let G be a finite group. We assume that an injective homomorphisms po: G + S. given. Then, G acts on R We say that map f: IR' - IR" is G-invrriant if f()()) = f(x) for any o E G and any x E Rm We also assume that th: G > Sn. Then, we say that a map f: Rm + RD G-equivariant if f(((o)) x) = v(a) f(x) for any G.
When G = S, and the actions are induced by permutation, we call G-invariant (resp. G-equivariant) functions permutation invariant (resp. permutation equivariant) functions.
3

---

Under review as a conference paper at ICLR 2020
21
2/2
Σ
P
Diagram I: A neural network approximating Sn-invariant function f. In blue: the inputs, in red: the output, green: and who have to be learned.
We define G-invariance and G-equivariance for deep neural networks. We can easily confirm that the models in Zaheer et al. (2017) satisfies these properties.
Definition 2.2. We say that a deep neural network Zμ o Zz-1... Zz. Z1 as T G-equivariant an action G on each of layers Rdd: given by embedding G + Sa, and the all corresponding map Zy: RR + Rd.-1 is G-equivariant. We say that deep neural network is G-invariant if there positive integer c H such that G-actions on each layer RRd, for S S are given and the corresponding map Ze RRd, Rd++1 is G-equivariant for 1 S 1 and the map Zo Rd. + Rd is G-invariant.
Some approximation theorems for invariant functions have been already known:
Proposition 2.1 (G-invariant version of universal approximation theorem). Let G be a finite group which a subgroup of Sn- Let K be a compact set The which is stable for the corresponding G-action in I" Then, for any f: K + R which is continuous and G-invariant and for any the following G-invariant ReLU neural networks Mfnv I + 12m satisfy that these represented functions Rag satisfy ||5
Ry 11 <
No = E o Lu o ReLU .... Tr, where Σ is the summation (G-invariant part) and L:: Raaixa. Ruatss xaits xar+ is a linear map such that Lilg X) = g L((X) for any
g E G and any E R xu, Here, the actions on each layers except for the output layer are same Example 2.2
For G= Sm. Ninn No E No) where N₂ (resp. No) is a deep neural network approximating (resp. 6) defined below.
This proposition for = S2 is proven by Zaheer al. 2017 Yarotsky (2018) For general finite group G, Maron et al. (2019b) proved it. Diagram illustrates the S,n-invrriant ReLU neural network
appeared in Proposition 2.1 The key ingredient of the proof by Zaheer et (0177) the following Kolmogorov-Amold representation theorem:
Theorem 2.1 (Zaheer et al. (2017) Kolmogorov-Amood's representation theorem for permutation
actions). Let K R be compact Then, any continuous S., S,-invariant function f: K + R can be represented as
Σ MIi)
for some continuous function p: 1R++1 + R.. Here, Φ: TR Ru+1, 1 (1, x,
Since dxx) has only one variable, line up the copies of the network which approximates ((x). Then, by combining V and the network which approximates we obtain the network which approxi- mates f. By using the theorem Hanin & Sellke (2017) (resp. Sonoda & Murata (2017)) obtain the bound the width (resp. the depth) for approximation of Φ and Maron et al. (001b) proved this proposition using tensor structure.
The main theorem G-equivariant version of universal approximation theorem. To state the main theorem, need some notation. Let G be finite group acting R.. We set the orbit decomposition
4

---

Under review as a conference paper at ICLR 2020
id
id
Diagram 2: neural network approximating S, -q.-equivariant map F
of (1,2,...,, as 21,2,... n = L Oi and let O;, = =iji = ij i22, Gg, Without loss of generality, we may reorder 21.2..... n as
O 11,2,....11),... 11+ 1,41 + 2, ..... +2)....
and i, = E + for 1,2,...,, m. For each j. let = Like Stabe (Tj be the coset decomposition by Staba(i;). Then, we may assume that Tj E G satisfies JjK (1,) = i; + k for = 112,....,44 Then, the main theorem is the following:
Theorem 2.2 (G-equivariant version of universal approximation theorem). Let G be a finite group which is subgroup of Sn- Let K be compact set in I which is stable for the corresponding G- which is continuous and G-equivariant requiv
action Ra Then, for any F:
IR;; x H (Si,..., and for any e > O, the following G-invariant ReLU neural network N
I - R2" satisfies that
these represented functions R Reguis satisfy ||F R Rygguis 1100
NG
fay requiv (tabe((h) T1,1,
fiuv (iab
T1,2
civ mmm.m.
(t..
Here, N fnv (i,) is the Staba -ivarrian deep neural network approximating fú, as in Proposition
2.1
and the actions on each layers are defined as follows: Each of hidden layers are written by
R
2R V for vector space V. On this space, E G acts on (æI,..., va) @ E R &R V
(x,
E by
a. ((21,, Dnn) 8 v) = (ō1,1 To)1(1)) m, az- 2
where Jj is the element of (tabori;) satisfying Jj. TJ,MOT,, for some k' =,1,,......
For G = S when Aequiv is represented by Z Z Z1 in that Zz...., Zh are S,, Su-equivariant by usual permutation. In this sense, our model is close to the S,, equuviiarr model in Zaheer et al. (2017).
consider
Our strategy for the proof is the following: At first, we establish the correspondence between (iabo(is)-invarts functions and G-equivariant functions. By this correspondence, take
5

---

Under review as a conference paper at ICLR 2020
(ta invariant function f corresponding to the objective function F. By Proposition 2.1
we can approximate I by a Staba -invarrran network Nany (6,)" Using N Miny (f,) we construct the G-equivariant network which approximates F. Diagram illustrates the S, Squ-euuivaraant ReLU neural network appeared in Theorem 2.2
Due our universal approximation theorems, if the free parameters of the invariant/equivariant mod- els are fewer than the ones of the usual models, we have guarantee for using the invariant/equivariant models. The following definition illustrates the swapping of nodes.
Definition 2.3. Let X = .I.....M 3 be an index set of nodes in a layer. We say an Sctactoon on X is union of permutations if X Xx, where each X; has elements and S,, acts on X; by permutation.
Theorem 2.3. Let N be an Sn, Sn-invariant model of depth D and width M whose number of the equivariant layers is d (resp. an Sn Sn-equivarian model of depth and width M). Assume that the action is a union of permulations on nodes in each equivariant layer: Then, the number of free parameters in this model is bounded by M2D (2/n2 (resp. M2D (2)
Note that the number of free parameters in the fully connected model is M2D Hence, this theorem implies that the free parameters of the invariant/equivarian models are far fewer than the ones of the usual models.
3 EQUIVARIANT CASE
In this section, we prove Theorem 2.2 namely, the equivariant version of the universal approximation theorem. The key ingredient is the following proposition (proof is in Appendix
Proposition 3.1. Notations are same as Theorem 2.2 Then, a map F; I2"" - IR is G-equivariant if and only if F can be represented by F = (f1 T1,1, f1 .1,2...... f mm invariant functions fJ RR" + R. Here, Tj E G is regarded as a linear map R PT.
Tmm...) ) for some Stabe (tz)-
For simplicity, we prove Theorem 2.2 only for G Sn,. We can show the general case by a similar argument. More precisely, we construct an Su-equivariant deep neural network approximating the given S, -quuivivari function. Similarly, we can prove this theorem for any finite group G. To show Theorem 2.2 for = Sn, we divide the proof to four steps as follows:
1. By Proposition 3.1 proved below, we reduce the argument on S, -qu-evuivrr map F to the one of Stab(1) (1)-invariant function f.
2. Modifying Theorem 2.1 we have representation of
function f. 3. Using the above representation, we have a Stab(1) (eab(()--invn i-inaariant deep neural net which approxi- mates and construct deep neural network approximating F.
4. We introduce certain action of S,, on (R")" which appears the first hidden layer naturally and show the Squeaaivrre between the input layer and the first hidden layer.
We first investigate step 1. We recall that, during this section, we only consider the action of S,, on R" induced from permutation the orbit of by this action is the total set O 21, ... n and the coset decomposition of S, by Stab(1) is S, = -. Stab(1) () i). Thus, we have the following:
(#1...., )x,) (I, (1))s-(1)s----. zx))()))" Then, we remark that
Corollary 3.1. A map F: R" - R is Sn-equivariam if and only if there is function f: Rn + R satisfying = (ʃ a 1), J1 (1 2),..., Im (1 n)) T. Here, (i E Sn is the transposition between i and and is regarled
linear map R R
Next, we consider step 2. The stabilizer subgroup Stab, (1) isomorphic Sn-1 as a group by Lemma. Hence, we can regard the Stab(1)- -invarart function f: R + I as an Sn-1-invarian function. This point of view allows us to apply Theorem 2. f. Hence, we have the following representation theorem of Stab(1 ) functions as a corollary of Theorem 2.1]
Corollary 3.2 (Representation of Stab(1) (lab(1)-invarian )-invariant function). Let K C RD be a compact set, let R be continuous and Stab(1) (1) -invariant function. Then, f(x) can be represented as f: K +
f(x) = f( ........)) = 11, Σ (xx;)

---

Under review as a conference paper at ICLR 2020
21
id
Σ
Tn
Diagram 3: A neural network approximating the Stab(()-invarian function ʃ
for some continuous function p: R - IR. Here, bb R + R" is similar as in Theorem 2.1
By this corollary, we can represent the Stab(1) (oooo(1--imm invariant function f IR" - + R as po=oooog where t R + RR (R")a-1 and L R (R2")=1 - R x R are
n x7
$ ((r1....... m.) (21, ((22).......... ... p(xn)). L(x, (y1..... 1n-1))
yi
Then, consider step 3, namely, the existence of Stabb()-innvriann deep neural network approx- imating the function f. After that, using this approximator, we construct a deep neural network approximating S, -quiiaaaat function F. By slight modification of the invariant version of Propo- case, there exists a sequence of deep neural networks {Am} Jm (resp. )Bm)m) which converges & (resp. p) uniformly. Then, the sequence of deep neural networks {Bm L a Am Jm converges to f po L o & uniformly.
sition 2.1 for (alab(1-innariinn
Now, f can be approached by the following deep neural network by replacing p and & by universal approximators as Diagram 3 We remark that the left part (the part of before taking sum) of this deep neural network is naturally equivariant for the action of Stab(1). For an S,,-quiivriaan map F R" + R" with the natural action, by Proposition 3.1 there is unique Stab 11) -iivirria function / such that F(x): = (ʃ o (1 i)) (z) Here, F(x) (F( r.))),) and we regard any element of Sn as map from R2 to IR". By the argument in this section, we can approximate I by the previous deep neural network (Bm o I, Am3m- Substituting Bm o L Am for S, we construct deep neural network approximating F Diagram
The represented function of this neural network of F; is Bm oo Am o i). The map F splits into two parts, the part of transpositions and part of corresponding to F as above, the latter part corresponds to the layers from the first hidden layer to the output layer. This part is the copies of same Stab(1), -nvvariann deep neural network (an approximation of (S, J. f) Thus, this part is clearly made of equivariant stacking layers for the permutation action of S.. Hence, it is remained to show that the former part is also S,,equivvriint..
On the deep neural network
We here investigate bounds of the width and the depth of approximators. By Theorem 2.1 each of ø and p can be approximated by shallow neural network. Hence, if do not bound the width, can obtain deep neural network approximating J' with depth three. On the other hand, by Theorem [2. again, if we do not bound the depth, (resp. p) can be approximated by a deep neural network with width + 1 (resp. n + 2). Thus, we can obtain a deep neural network approximating F with width bounded from above by n23
Finally, as step 4, we show that our deep neural network is an S, eqquivrriantt deep neural network. The most difficult part to show the equivariance between the input layer TR and the first hidden layer RR presented by a function g: R > RR" as (g1...., TT) for gi = ReLU o o (1 i) for certain Stab(11-invariant innvariant linear function 1: R + V. (Although V is equal to R., distinguish them to stress the difference.) Unfortunately, the permutation action on the latter space R= does not make the function g equivariant. For this reason, we need to define another action S, on R" exploiting the Stab(1 Jequivariaanc among each copies.
7

---

Under review as a conference paper at ICLR 2020
Definition 3.1. We suppose that Stab(1) acts IR by permutation, denoted by (i.e., by regarding Stab(1) as a subgroup of 5x). Then, we define the action "x" of S on R as follows:
σ (#1...... [n)) = (ō1 Lo (():) on Lo (m)) (Ta (1)
for any a E Sn, and for any (I1, 22 ;T,) = (Iia)).==l.... (IR"). Here, for any i, o. is an
element of Stab(1) defined as (1 i)0 0, (i)).
We will prove the well-definedness of this action "x" in Appendix D This action obtained by the injective homomorphism
:: Sn + S, a+ o(o), p(a) (1,5) (6,))
for (i.j) (1,2..... ..... n22. We remark that this action "*" naturally appears in representation theory as the induced representation, which an operation to construct representation of group S, from representation of the subgroup Stab(1) of Sn.
conclude the proof of Theorem 2.2 by showing the S, S,-equivariance of g:
Lemma 3.1. The function g: R" I="" Sx--euuivariant
The detail of proof is Appendix By this lemma, we conclude the proof of Theorem 2.2 We
remark that the affine transformation 9 is corresponding to Zı in the notation (I). By a representation theoretic aspect, this is an intertwining operator between these representation spaces. This affine transformation has n² free parameters a priori. However, by S, -qquivaarr and representation theoretic argument, in principle, can be written by only five parameters. By a similar argument, for the other hidden layers, the affine transformation Z, 1 &V, + R²" @ has 15 dim V; dim V parameters (though n dim V, dim V4+1 a priori).
DIMENSION REDUCTION
In this section, we give the proof of Theorem
2.3 Proposition 4.1. Let ReLU Wi RM Sn-action TR M and TR is union of permutations. Then, n divides M and N, and the number of the free parameters Wi equal 2M N/n?.
RN be an Squequvvrra map. Assume that the
Proof. Since RM and RN have union of permutation actions, by considering the orbit of the cordi- nates, that divides M and N. Let write RM (RR") and H (R") In this case, Wi is written by sum of n x n matrices Vij. namely Wt = (Viy))z=-- Here, each n x n matrix Vij corresponds to the linear map:
R" (R") 4, (R") R"
where the first map is the inclusion coordinates of (R")M' and the last map is projection to coordinates of (IR²) ( Since these constructions taken to be compatible with Sa-action,
that ReLU Vi is S,.-equivariant. the same discussion as in the proof of Lemma in Zaheer et al. (2017). But in our case, need more discussion, which is in Appendix G
the activation functions are bijective, we are done because of
Proof of Theorem 2.3 By Proposition the number of the free parameter in each equivariant layer
is bounded by 2M mn Hence we obtain the desired bound.
5 CONCLUSION
We introduced some invariant/equivariant models of deep neural networks which are universal approx- imators for invariant/equivarian functions. The universal approximation theorems in this paper and the discussion in Section show that although the free parameters our invariant/equivariant models are far fewer than the ones of the usual models, the invariant/equivariant models can approximate the invariant/equivariaat functions to arbitrary accuracy. Our theory also implies that there is much possibility that the group models behave the usual models for the tasks related to groups and representation theory can be powerful tool for theory machine learning. This must be a good perspective to develop the models in deep learning.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Krizhevsky Alex, Sutskever Sutskever, Ilya, and Hinton Geoffrey E. Imagenet classification with deep convolutional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Vladimir I. Arnol.. On functions of three variables. Proceeding the USSR Academy of Sciences, 114:679-681, 1957. English translation: Amer. Math. Soc. Transl., 28 (1963), pp. 51-54.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-133, 1994.
Benjamin Reddm and Yee Whye Teh. Probabilistic symmetry and invariant neural networks. arXiv preprint arXiv: 1901.06082, 2019. URL//ttps:://rxxiv.or////a/ /tt.b////91.00022222
Taco S Cohen and Max Welling. Group equivariant convolutional networks. Proceedings of the
33rd International Conference on Machine Learning, 4, 2016. URL: arXivpreprintarx.v
2.02.0756,, 2016.
George Cybenko.
Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 283):183-192, 1989.
Robert Gens and Pedro M Domingos. Deep symmetry networks. In Advances in Neural Information Processing Systems, pp. 2537-2545, 2014.
Ian Goodfellow, Yaroslav Bulatov, Julian Ibarz, Sacha Arnodd, and Vinay Shet. Multi-digit number recognition from street view imagery using deep convolutional neural networks. arXiv preprint arXiv:1312.6082, 2013.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:1710.11272 2017.
Jason Hartford, Devon Graham, Kevin Leyton-Brown and Siamak Ravanbakhsh. Deep models of interactions across sets. In International Conference on Machine Learning, pp. 1914-1923, 2018.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 2(5):359-366, 1989.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. arXiv preprint arXiv:/905. 04444,, 2019.
Andrey Nikolaevich Kolmogorov. On the representation of continuous functions of several variables by superpositions of continuous functions of smaller number of variables. Proceeding of the USSR Academy of Sciences, 108:176-182. 1956. English translation: Amer. Math. Soc. Transl., 17 (1961), pp. 369-373.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2747-2755, Stockholmsmässan. Stockholm Sweden, 10-15 Jul 2018. PMLR.
Vēra Kürková. Kolmogorov's theorem and multilayer neural networks. Neural networks, 5(3): 501-506, 1992.
Vēra Kürková and Marcello Sanguineti. Comparison of worst case errors in linear and neural network approximation. IEEE Transactions on Information Theory, 48(1) (8(1):264-277) 2002.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019a. URL https: ew. owt

---

Under review as a conference paper at ICLR 2020
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Proceedings of the 36th International Conference on Machine Learning, 97, 2019b.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 652-660, 2017.
Horace Pan Shubhendu Trivedi Brandon Anderson Risi Kondor, Hy Truong Son. Covariant composi- tional networks for learning graphs, 2018. URL http:p:://pppeeeeee.e.... net/ forum did=
S1TgE 7WR-
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)3354, 2017.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, 2017.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning, pp. 1058-1066, 2013.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arXiv preprint arXiv: 10306, 2018. URL:
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp- 3391-3401, 2017.
10

---

Under review as a conference paper at ICLR 2020
A REVIEW OF GROUPS AND GROUP ACTIONS
Let G be set with product, i.c., for any g. h E G, gh is defined an element of G. Then, is called group if G satisfies the following conditions:
1. There an element e E G such that eg ge = x for all g E G.
2. For any g E G, there an element g G such that 9g = 9 g =
3. For any 9, h, E G, (gh)i g(hi) holds.
Let G, G" be two finite groups. We say a map pi G G" is (group) homomorphism if p(gh) = (()))(h)) This means that the map y preserves the group structures of G in G'.
Next, we review actions of groups. Let X be a set. An action of (or G-action) on is defined as map G X X; (g.z) x) g satisfying the following:
1. For any x E X, 6
2. For any g, G and x E X, (gh): x == (h)..).
If these conditions are satisfied, we say that G acts on X by left action. Example A.1. An example which we mainly consider in this paper is the permutation group Sn of n elements:
S. = (o: [1,...,n] n - {1,..., n): bijective]
and the product of 0, S, is given by the composition n1, by the permutation a o
maps. Sn acts the set
We remark that actions of Sn on X is not unique, for example, the trivial action r for any E Sn, E X is also one of action. Hence, when we stress the difference of some actions, we use some distinguished notation for each actions as 4." or "*" etc.
Let G' be a group and H a subset of G. We call H a subgroup of G if H is a group with the same product G.
Example A.2. Let G be finite group acting a set X. For an element a E X, the stabilizer subgroup (taba(x) of with respects {a) defined by
Staba(r) = {g E G ggg-r=>
When G = Sn and 1, we use the following notation: Stab,,(1) Stab(1) := (tabo
Let G, G' be two groups. If there is an injective homomorphism ip: G G', the image (GG) C G' can be subgroup of G". Then, we say that is an embedding of group G to G'. Moreover, if G' acts on a set X, then G also acts on through yp, i.e., by ((r) for
and x E X.
Then, the following proposition holds:
Proposition A.1. Any finite group G can be embedded into for some n.
For any g E G. 99: 9, for some j (1,2,.... ... (i) = j. Then, we define a: G - Snig og. It is easy to show that this is an injective homomorphism.
Proof. Let n G and G {91. 92.... .n............ I.
as 99, E G. We set (
This proposition implies that any finite group G can be realized permutation action on R for some π.
Let G be finite group acting on X. Then, for X, we define the (G-)orbit Oz of x
O, G {g g E G).
Then, for x, y E X, the relation that x and are in a same orbit is an equivalent relation. Hence, X can be divided a disjoint union of the equivalent classes of this equivalent relation:
x

---

Under review as a conference paper at ICLR 2020
We call this the (G-)orbit decomposition of X.
Let H be a subgroup finite group G. Then, for E G, the set
gH {gh E G E H}
called the left coset of with respect to The relation that two elements g and g' are a same coset is also equivalent relation. Hence, divide G to disjoint union of equivalent classes of this relation:
G g.H.
We call this decomposition the right coset decomposition of G by H. We set G/H as the set of the left cosets of G by H:
G/H = {g1 H, 9..
Then, there is relation between orbit and set of cosets:
Proposition A.2. Let be a finite group acting on a set X. For x E X, the map
G/Staba(r) + Ozi (Stabo(z) + 9.95
is bijective.
Proof. It is easy to check well-definedness and bijectivity.
For G= Sn acting on (1,2....,n) nn), the G-orbit of 1 is only one, i.e., O1 {1.2, (1.,....,1) n.. Hence, the following holds (the permutation action of Sn is defined by taking inverse a hence we need to consider the of right cosets):
Corollary A.1. The map
(1){, - nt::..,,,,;a, 0
is bijective.
B PROOF OF PROPOSITION 2.1
Proof of Proposition 2.1 We may assume N 1. In fact, since we consider the - -norm, if all components of ||f Rrll is bounded by then Ilf lo I holds. For N 1, have f: K + R. Then, by Theorem 2.1 we obtain the representation of f as
f(z
Fn) = P Σ <b(x))
By the universal approximation property of ReLU deep neural network, we can find two sequences of ReLU deep neural network (N?) & and (N& such that their corresponding functions {FNz) g ) and {F (Fx } tend to p and for the -orm when tends to infinity. Let {N&}a be the sequence
of networks whose corresponding functions are FN2 (Z1,..., In) + (Fwg F
To show that {FNr b uniformly tends f. we use the following lemma:
Lemma B.1. If (f he tends uniformly to f. {gk he tends uniformly to g and f is uniformly continuous, then {fk o g&)b k tends uniformly to f g-
proof of Lemma B.I For any ki we have
Ifx o (x) ff g(x) = Ifk o (x(x) - fz ff fo g(x()
< fA o gx(x) - fo (x) +If (x(x) fog(z)).
-11-ff1
Let e > 0. By the uniform continuity of f. there 5 > 0 such that for all æ, y satisfying |x yl S 8, [f(x) f(v)] < e/2 holds. Then for large enough k, we have both || ol100 which implies g(x)l S c/2, and lff fllm S c/2. Hence, for any & large enough, [] gk f gll I holds.
that for any x, If gx
12

---

Under review as a conference paper at ICLR 2020
Now using Lemma B.1 we have that (41 (z1,...,,2)) Ei=1 (x.) tends to (I1....,22)) ..)
Ei=1 24 is Lipschitz (by triangular inequality) so uniformly continuous. Then, using Lemma B. again, we obtain the result, since p continuous on a compact set so uniformly continuous. Moreover, by [Sonoda & Murata (2017), we can approximate e and p by shallow networks. Hence, we have an approximation by a deep neural network N which has two hidden layers and the width is not bounded. By Hanin & Sellke (2017), we can respectively approximate each of & and p by some neural networks whose width are bounded by n 2 and the depth is not bounded. Hence, we have an approximation by deep neural network / whose width is bounded by nn + 2) and the depth is not bounded.
Ei=1 ((z;), because (zi,....,
The invariant function is approached by deep neural network / having the following diagram:
21
42
N
Σ
N
N
Let us show that this is a -i,-ivaarant deep neural network. Since the sum (Σ) is an invariant function, divide this neural network in parts the fist part on the left of the symbol Σ and the second on the right. For each layer Rd: of No there is a corresponding map Zi : Rd: + IR
Then for each layer (IR..)" of the first part of A,, there is a S, action a (I;); = (r)- for
= (2x); IR)d,, and the corresponding map (Z1, On the second part of NN, there is no S, actions on the layers RR except the trivial action. Hence, for this action, each corresponding map Zi IRd, - IRd+ is invariant. This shows that the network N Sn inniiaiaia
Zn) (Rd) - (IR..+1 )" is S,-equivariant.
C PROOF OF PROPOSITION 3.1
Proof of Proposition 3.1 First, we show that for (tabb((;)--ivarrt) function fj. the map
(f1 o 01,1, 1.2, ................................ fm mm ) R= is G-equivariant. Without loss of generality, we may assume that
On = (1,2,... ... ... O₂ = (4 + 1,4 + 4 12)
In particular, i, -E= 44 1. For each j, we set the coset decomposition by
G Stabo (it)
where may assume that тj, satisfies (7)((()) i k. Now, for G. there is unique k such that Ty A Hence, the (ij + k)-th entry becomes
f T o = In , o TFK = TT
On the other hand, we have
(i, + kk
J.k J. Tin + k) = K
This shows F is G-equivariant.
Conversely, we assume that F: ET + R" is G-equivariant. Let F = (g1. 99..9...... g. The orbit decomposition O.,...., Orm, is same as above. For a E G, by F(x) Fla x) for any æ E F. we have
.........
gi(a x) Go (2))
3
13

---

Under review as a conference paper at ICLR 2020
For simplicity, consider only for i = 1. Then, o (1) Oil thus 0-1 1,.... 11. By the equation (3) for a E Staba(1), we have
91(0 x) = (2)),
as a E Stabo(() and only o E Staba Hence, 91 is G-invariant. The equation (3) for TI,K
(k: = 1,2, 41) implies
g1 (T 3) = , (1) = (x).
This completes the proof for the orbit Oi By same arguments, we can prove the similar result for the other orbits.
D WELL-DEFINEDNESS OF THE ACTION "*"
We here show that the left action "x" of Sn on R²² defined in Section 3 is well-defined, i.e., for any T E Sn and any X = (x) ..... TT E R²" we have T * (a * x) (TO) * X.
The permutation group S, decomposed
S =
Stab(1)(1
For any a E Sn, because (1 (1)) is in Stab(1), this a is in the coset (tab(1)(1 (())) Apply this for (1 i)or for i, (1 i)or is in the coset
Stab(1) ((1))))- Stab
thus, we have unique element o, Stab(1) such that
(1 0
For O, E Sn and X = (z] ........20 2x)
E R" we have
σ . ((1)
Fiō+-1(1) to (6-1(())11))
T* x0) =
Tn Eo ((n)
नīनz 1(a) 1(7 1(1))
říō, 1(1) ((To) 1(1)
6.ē 1(m) I((r)) ((m))
Then, by the equation
σ. (1 i) 0 (i)). Hence we have
oo 10) = (1 (10=((=="000000000000000=0=
= (1 i)To(1 (i) (To);
This relation implies
-0+-1(1) : (17))-1(1) : (1) (m))
(TO), ((r))
(x
=(To) * X
(To), ((ro)-1(n))
Thus, the action is well-defined.
To satisfy the hypothesis of Theorem 2.3, need to check that the "*" action is free.
14

---

Under review as a conference paper at ICLR 2020
E
PROOF OF LEMMA 3.1
Proof of Lemma 3.1 For any i, any Sn and any IR", we have
(I (1 La x) (((((1)))) x).
Because for any i, there is a unique o; E Stab(1) such that (1 i)o = 5; (1)) as in Definition we have
3.1
[(((1 ()) x) = ((,,(10 o, 1((1 1((10 x)).
The last equality is due to of a g(x)) becomes
of I. On the other hand, by Definition 3.1 i-th entry
* ((*)())); = ō, (()
= o. (ReLU((((1 (i)) x))).
Because o; ReLU ReLU o o; holds, is S, -eeeqivvari
F DATA AUGMENTATION
Data augmentation a common technique empirical learning. In the case of the invari- ant/equivariant tasks, possible augmentation is make new samples by the acting permutation samples. New samples are effective to the usual models, but not effective to our invariant/equivariant models. This is because in models, all weights symmetric under permutation actions. This means that our models learn augmented samples from sample. By acting permutations, we can make nl! new samples from sample. Hence, computational complexity reduced to 1/n! times.
G DIMENSION REDUCTION
In this section, we give the proof of Proposition 4.1
Proof of Proposition 4.1 Since the action on M INN is union of permutations on nodes in each equivariant layer, we can write R.M the following form;
(Te²) M' and N = (R" In this case, W; can be written as
Vn
V12
VIM
Vn1
V/2
VaM
W,
:
VMe1
VM'2
VN
where Vij are X matrices. Let us consider the following maps:
R" (R 2, (R R
where the first map is the inclusion to the coordinates started from the (j - 1)n th coordinate of (R")M' ended at the jn 1 th coordinate of (IR") and the last map is the projection to the coordinates started from the (i 1)n th coordinate of (TR") ended the in 1 th coordinate of
15

---

Under review as a conference paper at ICLR 2020
(R") "R")"" We chase the elements of these maps follows;
0
01
V11
V12 V22
Viar Vear
02
02
V21
a2
po 0i
p Z
p
ReLU
On
VN1
VN22
VN
an
01
02
O Vij
On
022
p
ReLU o Vij
a1
02
ReLU o Vars
On
Hence, each n X n matrix Vij induces a subneural network. Since these constructions are taken compatible with -,cactio,, we see that f ReLU o ViJ R - Rx S, -quuqvvrari If the activation functions are bijective, we are done because of the same discussion in the proof of Lemma 3 in Zaheer et al. (2017). But since ReLU functions are not bijective, we need more discussion. Let us take transposition (p q). Since f is Sn -equivariant, f(x) = f' x) holds for any ac We have
011
@11
Oin
F1
201
ap1
apn
ap1
apn
T2
272
0 (x)
o
ReLU
0gl
aqn
Qg1
agm
En
an1
Onn
ap1
Σj=1 (1jzj
Σラ=1 01jay
a
Σ apj
Σ/=1 Iz
I1
ag1
agn
J2
ReeLU
-ReLU
=ReLU
- Unj
Σj = Unj
ap1
apn
En Onjiz
Σ anzZy
On
ann
16

---

Under review as a conference paper at ICLR 2020
On the other hand, we have
21
21
a1l
dip
0ig
Gin
Zig
d21
U2p
02n
a2n
((oox)=
= ReLU
Zy
3p
0n1
amp
agg
Onn
:
Fn
Zn.
301
dn
01g
01p
O1n
Fp
a2
02g
02p
d2
= ReLU
Gn1
ang
Omp
Onn
Zn.
d11
d1n
011
Q1q
01p
Q1n
ag1
Qg
021
02g
02p
Q2n
Claim 1.
apl
Pm
On1
ang
anp
Oyn
On1
Onn
Proof of Claim I. We have
Q11
Blg
alp
ain
agl
agn
Zp
D2
021
a2
a2p
0gn
ReLU
ReLU
apl
Opm
Tn
anl
Ong
anp
ann
0n1
ayn
In
for any Hence, the the -th coordinate of the left hand side is positive if and only if the one of the right hand side is positive.It clear that each equation is positive for infinitely many æ. This implics that the coefficients of each equations coincide. Hence, we have the desired result.
We show that app Ggg holds for any p. 9. We can see that the (p g) entry of the matrix of the left hand side in the claim is equal app. Similarly, the (p q) entry of the matrix of the right hand side in the claim is equal to agg- Hence, by the claim, we have app agg. We show that if of j and A I, as ast holds. Consider the (i q) entry of each matrices, the one the left hand side is equal to aip and the one of the right hand side is equal to aig. Hence, we have aip- Gig. where o p anc i * q. By the symmetry, api = ags holds for any # p and of Hence, we have
aj = a, Out
for any i + and * t. Hence, we can write ViJ = AI + (11
17


Reviews:
[{"review_id": "rklrHsfJ5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes a universal approximation theorem for functions invariant and equivariant to finite group actions. It constructs the approximations using fully-connected deep neural networks with ReLU activations. It proves a bound on the number of parameters in the build equivariant model. The proof structure uses a decompostion of G-equivariant functions into Stab(1)-invariant functions, which are represented by a particular network. \n\nThe proof structure is reasonably well written, however more context and examples could help a reader unfamiliar with the literature. This could be achieved by proposing applications of the construction of the approximating network to a few concrete applications where equivariant representations are needed.\n\nAs-is the paper is difficult for a newcomer to the field, compared e.g. with (Maron et al. 2019b) and (Keriven & Peyré 2019) which have clearer expositions. On the other hand, the equivariant representation problem is given in more generality, stemming from finite group actions represented by actions of permutation groups.\n\nMy current assessment is “borderline” and might change in light of author responses and reviews from reviewers with more experience in this field to judge the significance of the results.\n\nI think it is necessary to do a more in-depth comparison with respect to the existing work of (Keriven & Peyré 2019).\nIn this regard, I think the following could be done:\n- Giving an application and the corresponding construction where the increased generality w.r.t. the graph networks of (Keriven & Peyré 2019)\n- In the case of a graph network already addressed by (Keriven & Peyré 2019) , how would this construction apply and how would the constructed network compare?\n\nWhat do the authors call \"usual models\" in the discussion of Theorem 2.3? I assume this means models that do not exploit the equivariance of the function, but this could be more explicit.\n\nTypos:\np.5, in the discussion of Theorem 2.1: \"> Then, by ... we may assume\"\np.8, Prop 4.1 Proof: n devides M\np.11: Prop A.1 Proof: can be realized as a permutation action on R^n: R should be in \\mathbb\np.17: “ane” instead of “and”\n\n***\nUpdated review\n\nI have the impression all 3 reviewers have had some trouble going through the main messages of the paper. Although - at least in my case - this might be partly due to limited in-depth expertise, this seems to indicates some deeper shortcomings in the writing, as well as the insights and intuitions offered by the paper, in order to be accessible to a larger audience.\n\nI still believe the approach may have merits, however I do not recommend acceptance of the paper at its current state. In my opinion, the following points should be considered for a future resubmission:\n* A friendlier introduction to the matter with more intuitions and examples where the method has interest and distinguishes itself from existing papers, e.g. (Maron et al. 2019b), (Keriven & Peyré 2019) (Review #2, review #3)\n* At least 1 example (and possibly more) where the proposed method leads to a practical architecture (Review #1)\n* A clearer explanation of the particular role played by Sn w.r.t. general finite groups in the construction (Review #1)\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlwDP3aYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "*Paper summary* \n\nThe authors develop a universal approximation theorem for neural networks that are symmetric with respect to the symmetric group (permutations). They also formally show that the number of free parameters is to train an equivariant network is smaller that the number in a non-equivariant network, leading to better sample complexity.\n\n*Paper decision* \n\nI have decided to give this paper a weak reject. The contributions are clear and the paper is written well enough for publication. That said, the significance of the contribution is not clear to me, since there are other papers in the literature doing the same.\n\nI must admit that the subject material is out of my region of expertise, so my judgement may be a little miscalibrated.\n\n*Supporting arguments and questions for the authors* \n\nThe paper is clearly written by people who have a firm grasp of their subject. The contributions are well laid out and the following proofs are clearly placed in the paper. In terms of constructive criticism, I think it would be helpful to readers to give an intuition behind why the contributions are necessary and to add a sense of the motivation behind them. This would open up the paper to a broader audience.\n\nFor me, something that was not clear was how exactly this work is different from Zaheer et al., (2017). It would be nice if these differences were spelled out for me. It was also not clear why it was necessary to present the contribution that with each symmetry you introduce you reduce the number of parameters exponentially? I guess the intuition behind this is clear, but I was wondering why this is necessary to spell out with a Theorem (2.3 I believe). What exactly doe this result imply?\n\nIn terms of clarity, the preliminaries section is well written and quite clear. I enjoyed the summary. That said, it is quite advanced, and it would be useful to point more novice readers to elementary texts, where they could brush up on their group theory. Furthermore, the grammar in places is a bit tenuous, but on the whole the writing is understandable.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJxLzccRYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes a universal approximator for functions equivariant to finite group action. The idea is to draw a bijection between such equivariant universal approximators and those for functions that are “invariant” to the stabilizer subgroup of the output indices. Using existing results for designing universal invariant approximators, the paper then seems to suggest universal equivariant approximators in the form of neural networks. \n\nWhile this is an important topic and the paper -- to the extent that I could follow -- seems to be technically sound, I found the paper very hard to read in part due to numerous grammatical errors.\n\nAnother issue is that I don’t see why the symmetric group is treated separately from the general finite groups. If in the end, the goal is to plug in “a” universal G-invariant function, the paper could leave those details out and focus on clarifying its proposed bijection. Could you please comment? Also is there a setting in which this setup leads to a practical architecture?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article studies universal approximation for the restricted class of equivariant functions, which can have a smaller number of free parameters. The reviewers found the topic important and also that the approach has merits. However, they pointed out that the article is very hard to read and that more intuitions, a clearer comparison with existing work, and connections to practice would be important. The responses did clarify some of the differences to previous works. However, there was no revision addressing the main concerns. 

Decision: Reject