Title: UNIVERSAL APPROXIMATIONS OF PERMUTATION IN-VARIANT/EQUIVARIANT FUNCTIONS BY DEEP NEURAL NETWORKS

Abstract: In this paper, we develop a theory about the relationship between Ginvariant/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 far fewer free parameters than usual models.

1. INTRODUCTION:

Deep neural networks have great success in many applications such as image recognition, speech recognition, natural language process and others as Alex et al. (2012) , Goodfellow et al. (2013) , Wan et 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 is the so-called curse of dimensionality. Namely, if 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 et al. (2017) designed a model adapted to machine learning tasks defined on 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/equivariant networks as Qi et al. (2017) , Hartford et al. (2018) , Risi Kondor (2018) , Maron et al. (2019a) , Bloem-Reddy & Teh (2019) , Kondor & Trivedi (2018) , and so on. Nevertheless, theoretical guarantee of their methods is not sufficiently considered. One of our motivations is to establish a theoretical guarantee. In this paper, we prove an invariant/equivariant version of the universal approximation theorem by constructing an approximator. For the symmetric group, our 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 our invariant/equivariant model, and show that this number is far fewer than one of the usual models.

For usual deep neural networks, a universal approximation theorem was first proved by Cybenko (1989) . It states that, when the width goes to infinity, a (usual) neural network with a 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 Barron (1994) , Hornik et al. (1989) , Funahashi (1989) , Kůrková & Sanguineti (2002) , and Sonoda & Murata (2017) . In particular, for a 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 without the universal approximation theorem. Our universal approximation theorem allows us 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 Stab G (i)-invariant functions. Here, G is a finite group and Stab G (i) is the subgroup of G consisting of the elements which fix i. We first confirm this correspondence at the function level. After that, we rephrase it by deep neural networks. This correspondence enables us to reduce the equivariant case to the invariant case.

The invariant case has already established by some researchers Zaheer et al. (2017) , Yarotsky (2018 ), Maron et al. (2019b) . For G = S n , here S n is the symmetric group of degree n, Zaheer et al. (2017) showed that a representation theorem of S n -invariant function which is famous as a solution for the Hilbert's 13th problem by Kolmogorov (1956) and Arnold (1957) gives us an explicit description. Due to this theorem and the usual universal approximation theorem, we can construct a concrete deep neural network of the invariant model. Recently, Maron et 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.

1.1 CONTRIBUTIONS Our contributions are summarized as 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 or more generally group actions.

• Using representation theory, we calculate the number of free parameters appearing in our models. As a result, the number of parameter in our 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 = S n , our theorem guarantees that our model for finite group G can approximate any Ginvariant/equivariant functions.

1.2. RELATED WORKS:

Group theory, or symmetry is 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 a natural generalization of convolutional neural networks that reduces sample complexity by exploiting symmetries. The models for permutation invariant/equivariant 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 the sigmoid function to a larger class of activation functions as Barron (1994) , Hornik et al. (1989) , Funahashi (1989) , Kůrková (1992) and Sonoda & Murata (2017) .

As mentioned above, the invariant case has been established. For G = S n , Zaheer et al. (2017) essentially proved an invariant version of an universal approximation theorem. Yarotsky (2018) gave a more explicit S n -invariant 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 G by shallow (hyper-)graph neural networks is proved by Keriven & Peyré (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, ours 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é (2019) .

2. PRELIMINARIES AND MAIN RESULTS:

In this paper, we treat fully connected deep neural networks. We mainly consider ReLU activation functions. Here, the ReLU activation function is defined by ReLU(x) = max(0, x). We remark that our argument during this paper works for any activation functions which satisfy a usual universal approximation theorem. A deep neural network is built by stacking the blocks which consist of a linear map and a ReLU activation. More formally, it is a function

Z i from R di to R di+1 defined by Z i (x) = ReLU(W i x + b i ), where W i ∈ R di+1×di , b i ∈ R di+1

. In this case, d i is called the width of the i-th layer. The output of the deep neural networks is

EQUATION

where H is 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 n be the group consisting of permutations of n elements {1, 2, . . . , n}. This S n is called the symmetric group of degree n. The symmetric group S n acts on {1, 2, . . . , n} by the permutation i → σ -1 (i) for σ ∈ S n . By Proposition A.1 that any finite group G can be regarded as a subgroup of S n for a positive integer n. Then, G also acts on {1, . . . , n} by the action as an element of S n . For i ∈ {1, 2, . . . , n}, we define the orbit of i as

O i = G(i) = {σ(i) | σ ∈ G}.

Then, the set {1, 2, . . . , n} can be divided to a disjoint union of the orbits: {1, 2, . . . , n}

= m j=1 O ij .

Let G be a finite group action on {1, 2, . . . , n}. For i = 1, 2, . . . , n, we define the stabilizer subgroup Stab G (i) of G associated with x by the subgroup of elements of G fixing i. Then, by Proposition A.2, the orbit O i and the set of cosets G/Stab G (i) are bijective. When G = S n , X = {1, 2, . . . , n}, and x = 1, we set Stab n (1) = Stab(1) := Stab G (x).

We next consider an action of S n on the vector space R n . The left action "•" of S n on R n is defined by σ

• x = σ • (x 1 , x 2 , . . . , x n ) = (x σ -1 (1) , x σ -1 (2) , . . . , x σ -1 (n) )

for σ ∈ S n and x = (x 1 , . . . , x n ) ∈ R n . We also call this the permutation action of S n on R n . If there is an injective group homomorphism ϕ : G → S n , G acts on R n by the permutation action as an element of S n by ϕ: For σ ∈ G and x ∈ R n , we define σ • x := ϕ(σ) • x. Then, we simply say that G acts on R n .

Example 2.1. The finite group G = S 2 is embedded into S 3 by ϕ : (1 2) → (1 2), where (i j) is transposition between i and j. In this case, the orbit decomposition of {1, 2, 3} is {1, 2} {3}. By this embedding ϕ, an S 2 -action on R 3 is defined:

ϕ((1 2)) • (x 1 , x 2 , x 3 ) = (x 2 , x 1 , x 3 ) .

Example 2.2 (Tensors). The group action of G which is a subgroup of S n on tensors as in Maron et al. ( 2019b) is realized as follows: An S n -action on R n k ×a is defined by the following injective homomorphism ϕ : G → S an k : We fix a bijection from {1, . . . , an k } to {1, . . . , n} k × {1, 2, . . . , a}, and for σ ∈ S n , ϕ(σ) ∈ S an k is defined by

ϕ(σ) • (i 1 , . . . , i k , j) = (σ -1 (i 1 ), . . . , σ -1 (i k ), j) for (i 1 , . . . , i k ) ∈ {1, . . . , n} k and j ∈ {1, 2, . . . , a}.

Then, for a tensor

X = (x i1,...,i k ,j ) i1,...,i k =1...,n, j=1,2,...,a ∈ R n k ×a , σ ∈ S n acts on R n k ×a by ϕ(σ) • X = (x σ -1 (i1),...,σ -1 (i k ),j

). This action is same as one of Maron et al. (2019b) . Example 2.3 (n-tuple of D-dimensional vectors). We identify {1, 2, . . . , nD} with {(i, j) | i = 1, . . . , n, j = 1, . . . , D} and define ϕ :

S n → S nD as ϕ(σ)•(i, j) = (σ -1 (i), j). Let (x 1 , . . . , x n ) ∈ (R D ) n be an n-tuple of D-dimensional vectors. Then, for σ ∈ S n , φ(σ) • (x 1 , . . . , x n ) = (x σ -1 (1) , . . . , x σ -1 (n) )

. This means a permutation of n vectors. Definition 2.1. Let G be a finite group. We assume that an injective homomorphisms ϕ : G → S m are given. Then, G acts on R m . We say that a map f :

R m → R n is G-invariant if f (ϕ(σ)•x) = f (x)

for any σ ∈ G and any x ∈ R m . We also assume that ψ : G → S n . Then, we say that a map

f : R m → R n G-equivariant if f (ϕ(σ) • x) = ψ(σ) • f (x) for any σ ∈ G.

When G = S n and the actions are induced by permutation, we call G-invariant (resp. G-equivariant) functions as permutation invariant (resp. permutation equivariant) functions.

ρ . . . . . . . . . φ x n φ x 2 φ x 1

Diagram 1: A neural network approximating S n -invariant function f . In blue: the inputs, in red: the output, in 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 H • Z H-1 . . . Z 2 • Z 1 as (1) is G-equivariant if an action of G on each of layers R di is given by embedding G → S di and the all corresponding map Z i : R di → R di+1 is G-equivariant. We say that a deep neural network is G-invariant if there is a positive integer c ≤ H such that G-actions on each layer R di for 1 ≤ i ≤ c + 1 are given and the corresponding map Z i : R di → R di+1 is G-equivariant for 1 ≤ i ≤ c -1 and the map Z c : R dc → R dc+1 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 is a subgroup of S n . Let K be a compact set in R n which is stable for the corresponding G-action in R n . Then, for any f : K → R m which is continuous and G-invariant and for any > 0, the following G-invariant ReLU neural networks

N inv G : R n → R m satisfy that these represented functions R N inv G satisfy f -R N inv G ∞ < : • N inv G = Σ • L H • ReLU • • • • • L 1 , where Σ is the summation (G-invariant part) and L i : R n d i ×ai → R n d i+1 ×ai+1 is a linear map such that L i (g • X) = g • L i (X) for any g ∈ G and any X ∈ R n d i ×ai .

Here, the actions on each layers except for the output layer are same as Example 2.2.

• For G = S n . N inv G = N ρ • Σ • (N φ , . . . , N φ ) , where N ρ (resp. N φ ) is a deep neural network approximating ρ (resp. φ) defined below.

This proposition for G = S n is proven by Zaheer et al. (2017) , Yarotsky (2018) 

). Let K ⊂ R n be a compact set. Then, any continuous S n -invariant function f : K → R can be represented as f (x 1 , . . . , x n ) = ρ n i=1 φ(x i ) (2)

for some continuous function ρ : R n+1 → R. Here, φ : R → R n+1 ; x → (1, x, x 2 , . . . , x n ) .

Since φ(x) has only one variable, we line up the copies of the network which approximates φ(x).

Then, by combining Σ and the network which approximates ρ, we obtain the network which approximates f . By using the theorem of 

O i1 = {1, 2, . . . , l 1 }, O i2 = {l 1 + 1, l 1 + 2, . . . l 1 + l 2 }, . . . and i j = j-1 k=1 l k + 1 for j = 1, 2, . . . , m. For each j, let G = lj k=1

Stab G (i j )τ j,k be the coset decomposition by Stab G (i j ). Then, we may assume that τ j,k ∈ G satisfies τ -1 j,k (i j ) = i j + k for k = 1, 2, . . . , l j . 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 a subgroup of S n . Let K be a compact set in R n which is stable for the corresponding Gaction in R n . Then, for any F : K → R n ; x → (f 1 , . . . , f n ) which is continuous and G-equivariant and for any > 0, the following G-invariant ReLU neural network N equiv

G : R n → R n satisfies that these represented functions R N equiv G satisfy F -R N equiv G ∞ < : N equiv G = (N inv Stab G (i1) • τ 1,1 , N inv Stab G (i1) • τ 1,2 , . . . , N inv Stab G (im) • τ m,lm ) .

Here,

N inv Stab G (ij ) is the Stab G (i j )-invariant deep neural network approximating f ij as in Proposition 2.

1, and the actions on each layers are defined as follows: Each of hidden layers are written by R n 2 ⊗ R V for a vector space V . On this space, σ ∈ G acts on (x 1 , . . . ,

x n ) ⊗ v ∈ R n 2 ⊗ R V (x i ∈ R n ) by σ • ((x 1 , . . . , x n ) ⊗ v) = ( σ 1,1 • x σ -1 (1) , . . . , σ m,lm • x σ -1 (n) ) ⊗ v,

where σ j,k is the element of Stab G (i j ) satisfying σ j,k = τ j,k στ -1 j,k for some k = 1, 2, . . . , l j . 1), we can consider that Z 2 , . . . , Z H are S n -equivariant by usual permutation. In this sense, our model is close to the S n -equivariant model in Zaheer et al. (2017) .

For G = S n , when N equiv G is represented by Z H • Z H-1 • • • • • Z 1 as in (

Our strategy for the proof is the following: At first, we establish the correspondence between Stab G (i j )-invariant functions and G-equivariant functions. By this correspondence, we take Stab G (i j )-invariant function f corresponding to the objective function F . By Proposition 2.1, we can approximate f by a Stab G (i j )-invariant network N inv Stab G (ij ) . Using N inv Stab G (ij ) , we construct the G-equivariant network which approximates F . Diagram 2 illustrates the S n -equivariant ReLU neural network appeared in Theorem 2.2. Due to our universal approximation theorems, if the free parameters of the invariant/equivariant models are fewer than the ones of the usual models, we have a guarantee for using the invariant/equivariant models. The following definition illustrates the swapping of nodes. Definition 2.3. Let X = {1, . . . , M } be an index set of nodes in a layer. We say an S n -action on X is a union of permutations if X = X i , where each X i has n elements and S n acts on X i by permutation. Theorem 2.3. Let N be an S n -invariant model of depth D and width M whose number of the equivariant layers is d (resp. an S n -equivariant model of depth D and width M ). Assume that the action is a union of permutations on nodes in each equivariant layer. Then, the number of free parameters in this model is bounded by

M 2D • (2/n 2 ) d (resp. M 2D • (2/n 2 ) D ).

Note that the number of free parameters in the fully connected model is M 2D . Hence, this theorem implies that the free parameters of the invariant/equivariant 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 C): Proposition 3.1. Notations are same as Theorem 2.2. Then, a map

F : R n → R n is G-equivariant if and only if F can be represented by F = (f 1 • τ 1,1 , f 1 • τ 1,2 , . . . , f m • τ m,lm ) for some Stab G (i j )- invariant functions f j : R n → R. Here, τ j,k ∈ G is regarded as a linear map R n → R n .

For simplicity, we prove Theorem 2.2 only for G = S n . We can show the general case by a similar argument. More precisely, we construct an S n -equivariant deep neural network approximating the given S n -equivariant function. Similarly, we can prove this theorem for any finite group G. To show Theorem 2.2 for G = S n , we divide the proof to four steps as follows:

1. By Proposition 3.1 proved below, we reduce the argument on S n -equivariant map F to the one of Stab(1)-invariant function f . 2. Modifying Theorem 2.1, we have a representation of Stab(1)-invariant function f . 3. Using the above representation, we have a Stab(1)-invariant deep neural net which approximates f and construct a deep neural network approximating F . 4. We introduce a certain action of S n on (R n ) n which appears the first hidden layer naturally and show the S n -equivariance 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 n on R n induced from permutation σ • (x 1 , . . . , x n ) = (x σ -1 (1) , . . . , x σ -1 (n) ) . Then, we remark that the orbit of 1 by this action is the total set O 1 = {1, 2, . . . , n} and the coset decomposition of S n by Stab( 1) is S n = n i=1 Stab(1)(1 i). Thus, we have the following:

Corollary 3.1. A map F : R n → R n is S n -equivariant if and only if there is Stab(1)-invariant function f : R n → R satisfying F = (f • (1 1), f 1 • (1 2), . . . , f m • (1 n)) .

Here, (i j) ∈ S n is the transposition between i and j and is regarded as a linear map R n → R n .

Next, we consider step 2. The stabilizer subgroup Stab n (1) is isomorphic to S n-1 as a group by Lemma. Hence, we can regard the Stab(1)-invariant function f : R n → R as an S n-1 -invariant function. This point of view allows us to apply Theorem 2.1 to f . Hence, we have the following representation theorem of Stab(1)-invariant functions as a corollary of Theorem 2.1. Corollary 3.2 (Representation of Stab(1)-invariant function). Let K ⊂ R n be a compact set, let f : K -→ R be a continuous and Stab(1)-invariant function. Then, f (x) can be represented as

f (x) = f (x 1 , . . . , x n ) = ρ x 1 , n i=2 φ(x i ) , ρ . . . . . . . . . φ x n φ x 2 id x 1 id

Diagram 3: A neural network approximating the Stab(1)-invariant function f

for some continuous function ρ : R n+1 -→ R. Here, φ : R → R n is similar as in Theorem 2.1.

By this corollary, we can represent the Stab(1)-invariant function f :

R n -→ R as f = ρ • L • Φ, where Φ : R n → R × (R n ) n-1 and L : R × (R n ) n-1 → R × R n are Φ(x 1 , . . . , x n ) = (x 1 , φ(x 2 ), . . . , φ(x n )), L(x, (y 1 , . . . , y n-1 )) = x, n-1 i=1 y i .

Then, we consider step 3, namely, the existence of Stab(1)-invariant deep neural network approximating the function f . After that, using this approximator, we construct a deep neural network approximating S n -equivariant function F . By a slight modification of the invariant version of Proposition 2.1 for Stab(1)-invariant case, there exists a sequence of deep neural networks {A m } m (resp. {B m } m ) which converges to Φ (resp. ρ) uniformly. Then, the sequence of deep neural networks

{B m • L • A m } m converges to f = ρ • L • Φ uniformly.

Now, f can be approached by the following deep neural network by replacing ρ 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 n -equivariant map F : R n → R n with the natural action, by Proposition 3.1, there is a unique Stab(1)-invariant function f such that F (x) i = (f • (1 i))(x). Here, F (x) = (F (x) 1 , . . . , F (x) n ) and we regard any element of S n as a map from R n to R n . By the argument in this section, we can approximate f by the previous deep neural network

{B m • L • A m } m . Substituting B m • L • A m for f , we construct a deep neural network approximating F as Diagram 2.

The represented function of this neural network of

F i is B m • L • A m • (1 i).

The map F splits into two parts, the part of transpositions and part of (f, f, . . . , f ) . On the deep neural network 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 n copies of same Stab(1)-invariant deep neural network (an approximation of (f, f, . . . , f ) ). Thus, this part is clearly made of equivariant stacking layers for the permutation action of S n . Hence, it is remained to show that the former part is also S n -equivariant.

We here investigate bounds of the width and the depth of approximators. By Theorem 2.1, each of φ and ρ can be approximated by a shallow neural network. Hence, if we do not bound the width, we can obtain deep neural network approximating F with depth three. On the other hand, by Theorem 2.1 again, if we do not bound the depth, φ (resp. ρ) can be approximated by a deep neural network with width n + 1 (resp. n + 2). Thus, we can obtain a deep neural network approximating F with width bounded from above by n 3 .

Finally, as step 4, we show that our deep neural network is an S n -equivariant deep neural network.

The most difficult part is to show the equivariance between the input layer R n and the first hidden layer R n 2 presented by a function g : R n → R n 2 as g = (g 1 , . . . , g n ) for g i = ReLU • l • (1 i) for a certain Stab(1)-invariant linear function l : R n → V . (Although V is equal to R n , we distinguish them to stress the difference.) Unfortunately, the permutation action on the latter space R n 2 does not make the function g equivariant. For this reason, we need to define another action of S n on R n 2 exploiting the Stab(1)-equivariance among each copies. Definition 3.1. We suppose that Stab(1) acts on R n by permutation, denoted by σ • x (i.e., by regarding Stab(1) as a subgroup of S n ). Then, we define the action " * " of S n on R n 2 as follows:

σ * (x 1 , . . . , x n ) = (σ 1 • x σ -1 (1) , . . . , σn • x σ -1 (n) ) = (x σ -1 j (i),σ -1 (j)

) i,j=1,...,n for any σ ∈ S n , and for any (x 1 , x 2 , . . . , x n ) = (x i,j ) i,j=1,...,n ∈ (R n ) n . Here, for any i, σi is an element of Stab(1) defined as (1 i)σ = σi (1 σ -1 (i)).

We will prove the well-definedness of this action " * " in Appendix D. This action is obtained by the injective homomorphism ϕ : S n → S n 2 ; σ → ϕ(σ), ϕ(σ) • (i, j) = ( σ -1 j (i), σ -1 (j)) for (i, j) ∈ {1, 2, . . . , n} 2 . We remark that this action " * " naturally appears in representation theory as the induced representation, which is an operation to construct a representation of group S n from a representation of the subgroup Stab(1) of S n .

We conclude the proof of Theorem 2.2 by showing the S n -equivariance of g:

Lemma 3.1. The function g : R n → R n 2 is S n -equivariant.

The detail of proof is in Appendix E. By this lemma, we conclude the proof of Theorem 2.2. We remark that the affine transformation g is corresponding to Z 1 in the notation (1). By a representation theoretic aspect, this is an intertwining operator between these representation spaces. This affine transformation has n 3 free parameters a priori. However, by S n -equivariance and a representation theoretic argument, in principle, g can be written by only five parameters. By a similar argument, for the other hidden layers, the affine transformation

Z i : R n 2 ⊗V i → R n 2 ⊗V i+1 has 15 dim V i dim V i+1 parameters (though n 4 dim V i dim V i+1 a priori).

4. DIMENSION REDUCTION:

In this section, we give the proof of Theorem 2.3. Proposition 4.1. Let Z l = ReLU • W l : R M → R N be an S n -equivariant map. Assume that the S n -action on R M and R N is a union of permutations. Then, n divides M and N , and the number of the free parameters in W l is equal to 2M N/n 2 . Proof. Since R M and R N have union of permutation actions, by considering the orbit of the cordinates, we see that n divides M and N . Let us write

R M = (R n ) M and R N = (R n ) N . In this case, W l is written by sum of n × n matrices V ij , namely W l = (V ij ) n i,j=1

. Here, each n × n matrix V ij corresponds to the linear map:

R n → (R n ) M Z l -→ (R n ) N R n

, where the first map is the inclusion to coordinates of (R n ) M and the last map is projection to coordinates of (R n ) N . Since these constructions are taken to be compatible with S n -action, we see that ReLU • V ij is S n -equivariant. If the activation functions are bijective, we are done because of the same discussion as in the proof of Lemma 3 in Zaheer et al. (2017) . But in our case, we need more discussion, which is in Appendix G.

Proof of Theorem 2.3. By Proposition 4.1, the number of the free parameter in each equivariant layer is bounded by 2M 2 /n 2 . Hence we obtain the desired bound.

5. CONCLUSION:

We introduced some invariant/equivariant models of deep neural networks which are universal approximators for invariant/equivariant functions. The universal approximation theorems in this paper and the discussion in Section 4 show that although the free parameters of our invariant/equivariant models are far fewer than the ones of the usual models, the invariant/equivariant models can approximate the invariant/equivariant functions to arbitrary accuracy. Our theory also implies that there is much possibility that the group models behave as the usual models for the tasks related to groups and representation theory can be powerful tool for theory of machine learning. This must be a good perspective to develop the models in deep learning. Now using Lemma B.1, we have that (x 1 , . .

. , x n ) → n i=1 F N φ k (x i ) tends to (x 1 , . . . , x n ) → n i=1 φ(x i ), because (x 1 , . . . , x n ) → n i=1

x i is Lipschitz (by triangular inequality) so uniformly continuous. Then, using Lemma B.1 again, we obtain the result, since ρ is continuous on a compact set so uniformly continuous. Moreover, by Sonoda & Murata (2017) , we can approximate φ and ρ 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 ρ by some neural networks whose width are bounded by n + 2 and the depth is not bounded. Hence, we have an approximation by a deep neural network N whose width is bounded by n(n + 2) and the depth is not bounded.

The invariant function f is approached by a deep neural network N having the following diagram:

N ρ . . . . . . . . . N φ x n N φ x 2 N φ x 1

Let us show that this is a S n -invariant deep neural network. Since the sum (Σ) is an invariant function, we can divide this neural network in two parts : the fist part on the left of the symbol Σ and the second on the right. For each layer R di of N φ there is a corresponding map Z i : R di → R di+1 . Then for each layer (R di ) n of the first part of N , there is a S n action σ

• (x i ) i = (x σ -1 (i) ) i for x = (x i ) i ∈ R) di , and the corresponding map (Z 1 , • • • , Z n ) : (R di ) n → (R di+1 ) n is S n -equivariant.

On the second part of N , there is no S n actions on the layers R dj except the trivial action. Hence, for this action, each corresponding map Z i : R dj → R di+j is invariant. This shows that the network N is S n -invariant.

C PROOF OF PROPOSITION 3.1:

Proof of Proposition 3.1. First, we show that for Stab G (i j )-invariant function f j , the map

F = (f 1 • σ 1,1 , f 1 • σ 1,2 , . . . , f m • σ m,lm ) ∈ R n is G-equivariant.

Without loss of generality, we may assume that

O i1 = {1, 2, . . . , l 1 }, O i2 = {l 1 + 1, l 1 + 2, . . . , l 1 + l 2 }, . . . .

In particular, i j = j-1 k=1 l k + 1. For each j, we set the coset decomposition by

G = lj k=1 Stab G (i j )τ j,k ,

where we may assume that τ j,k satisfies τ -1 j,k (i j ) = i j + k. Now, for σ ∈ G, there is a unique k such that τ j,k σ = σ j,k τ j,k . Hence, the (ij + k)-th entry becomes

f j • τ j,k • σ = f j • σ j,k • τ j,k = f j • τ j,k .

On the other hand, we have

σ -1 (i j + k) = τ -1 j,k σ -1 j,k τ j,k (i j + k) = i j + k . This shows F is G-equivariant.

Conversely, we assume that F : R n → R n is G-equivariant. Let F = (g 1 , g 2 , . . . , g n ) . The orbit decomposition O i1 , . . . , O im is same as above. For σ ∈ G, by σ • F (x) = F (σ • x) for any x ∈ R n , we have

g i (σ • x) = g σ -1 (i) (x).

(3)

For simplicity, we consider only for i = 1. Then, σ -1 (1) ∈ O i1 , thus σ -1 (1) = 1, . . . , l 1 . By the equation ( 3), for σ ∈ Stab G (1), we have

g 1 (σ • x) = g 1 (x), as σ ∈ Stab G (1) if and only if σ -1 ∈ Stab G (1). Hence, g 1 is G-invariant. The equation (3) for τ 1,k (k = 1, 2, . . . , l 1 ) implies g 1 (τ 1,k • x) = g τ -1 1,k (1)(x) = g k (x).

This completes the proof for the orbit O i1 . 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 " * " of S n on R n 2 defined in Section 3 is well-defined, i.e., for any σ, τ ∈ S n and any X = (x 1 , . . . ,

x n ) ∈ R n 2 , we have τ * (σ * X) = (τ σ) * X.

The permutation group S n is decomposed as

S n = n i=1

Stab(1)(1 i).

For any

σ ∈ S n , because σ(1 σ -1 (1)) is in Stab(1), this σ is in the coset Stab(1)(1 σ -1 (1)). Apply this for (1 i)σ for i, (1 i)σ is in the coset Stab(1)(1 ((1 i)σ) -1 (1)) = Stab(1)(1 σ -1 (i)),

thus, we have a unique element σi ∈ Stab(1) such that

EQUATION

For σ, τ ∈ S n and X = (x 1 , . . . ,

x n ) ∈ R n 2 , we have τ * (σ * X) = τ *    σ1 • x σ -1 (1) . . . σn • x σ -1 (n)    =    τ1 στ -1 (1) • x σ -1 (τ -1 (1)) . . . τ1 στ -1 (n) • x σ -1 (τ -1 (n))    =    τ1 στ -1 (1) • x (τ σ) -1 (1) . . . τ1 στ -1 (n) • x (τ σ) -1 (n)   

Then, by the equation ( 4), σi = (1 i)σ(1 σ -1 (i)). Hence we have

τi στ -1 (i) = (1 i)τ (1 τ -1 (i))(1 τ -1 (i))σ(1 σ -1 (τ -1 (i))) = (1 i)τ σ(1 (τ σ) -1 (i)) = (τ σ) i . This relation implies τ * (σ * X) =    τ1 στ -1 (1) • x (τ σ) -1 (1) . . . τ1 στ -1 (n) • x (τ σ) -1 (n)    =     (τ σ) 1 • x (τ σ) -1 (1) . . . (τ σ) n • x (τ σ) -1 (n)     = (τ σ) * X

Thus, the action is well-defined.

To satisfy the hypothesis of Theorem 2.3, we need to check that the " * " action is free.

(R n ) N . We chase the elements of these maps as follows;

p • Z i • i         a 1 a 2 . . . a n         = p • Z i                                     0 . . . 0 a 1 a 2 . . . a n 0 . . . 0                        ReLU •     V 11 V 12 . . . V 1M V 21 V 22 . . . V 2M . . . . . . . . . . . . V N 1 V N 2 . . . V N M                       0 . . . 0 a 1 a 2 . . . a n 0 . . . 0                                     = p                 ReLU • V 1j     a 1 a 2 . . . a n     . . . ReLU • V M j     a 1 a 2 . . . a n                     = ReLU • V ij     a 1 a 2 . . . a n    

Hence, each n × n matrix V ij induces a subneural network. Since these constructions are taken to be compatible with S n -action, we see that f = ReLU • V ij : R → R is S n -equivariant. If the activation functions are bijective, we are done because of the same discussion as 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 a transposition σ = (p q). Since f is S n -equivariant, σ • f (x) = f (σ • x) holds for any x. We have x 1 x 2 . . .

σ • f (x) = σ             ReLU •            

                x 1 x 2 . . . x n                 = ReLU             σ •            

                x 1 x 2 . . . x n                 = ReLU              σ •              n j=1 a 1j x j . . . n j=1 a pj x j . . . n j=1 a qj x j . . . n j=1 a nj x j                           = ReLU                           n j=1 a 1j x j . . . n j=1 a qj x j . . . n j=1 a pj x j . . . n j=1 a nj x j                           = ReLU                        

x n                

.

On the other hand, we have

f (σ • x) = f                        

x 1 . . .

x q . . .

x p . . . x 1 . . .

x n                         = ReLU                

x q . . .

x p . . . x p . . .

x n                         = ReLU                

x q . . .

x n                        

. x p . . .

x q . . .

x n                        

for any x. Hence, the the l -th coordinate of the left hand side is positive if and only if the one of the right hand side is positive.It is clear that each equation is positive for infinitely many x. This implies that the coefficients of each equations coincide. Hence, we have the desired result.

We show that a pp = a qq holds for any p, q. We can see that the (p q) entry of the matrix of the left hand side in the claim is equal to a pp . Similarly, the (p q) entry of the matrix of the right hand side in the claim is equal to a qq . Hence, by the claim, we have a pp = a qq . We show that if i = j and s = t, a ij = a st holds. Consider the (i q) entry of each matrices, the one of the left hand side is equal to a ip and the one of the right hand side is equal to a iq . Hence, we have a ip = a iq , where i = p ane i = q. By the symmetry, a pi = a qi holds for any i = p and i = q. Hence, we have a ij = a sj = a st for any i = j and s = t. Hence, we can write V ij = λI + γ(11 ).

:



Figures and Tables:

11 . . . a 1p . . . a 1q . . . a 1n a 21 . . . a 2p . . . a 2q . . . a 2n . n1 . . . a np . . . a nq . . . a nn

11 . . . a 1q . . . a 1p . . . a 1n a 21 . . . a 2q . . . a 2p . . . a 2n . a n1 . . . a nq . . . a np . . . a nn

11 . . . a 1q . . . a 1p . . . a 1n a 21 . . . a 2q . . . a 2p . . . a 2n . n1 . . . a nq . . . a np . . . a nn 11 . . . a 1q . . . a 1p . . . a 1n a 21 . . . a 2q . . . a 2p . . . a 2n . n1 . . . a nq . . . a np . . . a nn

. For general finite group G, Maron et al. (2019b) proved it. Diagram 1 illustrates the S n -invariant ReLU neural network appeared in Proposition 2.1. The key ingredient of the proof by Zaheer et al. (2017) is the following Kolmogorov-Arnold representation theorem: Theorem 2.1 (Zaheer et al. (2017) Kolmogorov-Arnold's representation theorem for permutation actions

Table content: <table/>

ij , and let O ij = {i j1 = i j , i j2 , . . . , i jlj }. Without loss of generality, we may reorder {1, 2, . . . , n} as

Table content: <table><tr><td/><td/><td/><td>id</td><td/><td/></tr><tr><td/><td/><td/><td/><td>id</td><td/></tr><tr><td/><td/><td/><td>φ</td><td/><td/></tr><tr><td>x 1</td><td>. . .</td><td>. . .</td><td>. . .</td><td>. . .</td><td>ρ</td></tr><tr><td/><td/><td/><td>φ</td><td/><td/></tr><tr><td>. . .</td><td/><td/><td>. . .</td><td/><td>. . .</td></tr><tr><td>x n</td><td/><td/><td>id</td><td/><td/></tr><tr><td/><td/><td/><td/><td>id</td><td/></tr><tr><td/><td/><td/><td>φ</td><td/><td/></tr><tr><td/><td>. . .</td><td>. . .</td><td>. . .</td><td>. . .</td><td>ρ</td></tr><tr><td/><td/><td/><td>φ</td><td/><td/></tr><tr><td colspan="5">Diagram 2: A neural network approximating S</td><td/></tr></table>

Peer review (iclr2020):
*Paper summary* The 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. *Paper decision* I 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. I must admit that the subject material is out of my region of expertise, so my judgement may be a little miscalibrated. *Supporting arguments and questions for the authors* The 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. For 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? In 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.