Title: IMPROVED GENERALIZATION BOUND OF PERMUTATION INVARIANT DEEP NEURAL NETWORKS

Abstract: We theoretically prove that learning with permutation invariant deep neural networks largely improves their generalization performance. Learning problems with data that are invariant to permutations are frequently observed in various applications, for example, point cloud data and graph data. Numerous methodologies have been developed and they achieve great performances, however, understanding a mechanism of the performance is still a developing problem. In this paper, we derive a theoretical generalization bound for invariant deep neural networks with a ReLU activation to clarify their mechanism. Consequently, our bound shows that the main term of their generalization gap is improved by
n! where n is a number of permuting coordinates of data. Moreover, we prove that an approximation power of invariant deep neural networks can achieve an optimal rate, though the networks are restricted to be invariant. To achieve the results, we develop several new proof techniques such as correspondence with a fundamental domain and a scale-sensitive metric entropy.

1. INTRODUCTION:

A learning task with permutation invariant data frequently appears in various situations in data analysis. A typical example is learning on sets such as a point cloud, namely, the data are given as a set of points and permuting the points in the data does not change a result of its prediction. Another example is learning with graphs which contain a huge number of edges and nodes. Such the tasks are very common in various scientific fields (Ntampaka et al., 2016; Ravanbakhsh et al., 2016; Faber et al., 2016) , hence, numerous deep neural networks have been developed to handle such the data with invariance (Zaheer et al., 2017; Li et al., 2018a; Su et al., 2018; Li et al., 2018b; Yang et al., 2018; Xu et al., 2018) . The succeeding methods show that their networks for invariance can greatly improve the accuracy with a limited size of networks and data.

An important question with invariant data is to understand the reason for the empirical high accuracy from theoretical aspects. Since invariant data are high-dimensional in general, learning theory claims that the high-dimensionality reduces its generalization performance. However, the methods for invariant data achieve better accuracy, thus it contradicts the theoretical principle. Though several theoretical studies (Maron et al. (2019) and Sannai et al. (2019) ) prove a universal approximation property of neural networks for invariant data and guarantee that invariant deep neural networks have sufficient expressive power, the generalization power of the invariant deep neural networks is left as an open question.

In this paper, we prove a theoretical bound for generalization of invariant deep neural networks.

To show an overview of our result, we provide a simplified version as follows. We consider a supervised-learning problem with m pairs of observations (X i , Y i ) where X i are regarded as pdimensional vectors, and X i can divided to n coordinates and each of them have D = p/n dimension. Also, let f Sn denote a function by a deep neural network which satisfies an invariant property, f (x) = f (σ • x) holds for any x ∈ R n×D where σ is an arbitrary permutation of D-dimensional coordinates in x. Also, we define R m (f ) = m -1 m i=1 L(Y i , f (X i )) and R(f ) = E[L(Y, f (X))] as an empirical and expected loss value L(Y, f (X)). Then, we show that following:

Theorem 1 (Informal version of Theorem 2). Let f Sn be a function by a deep neural network which takes p-dimensional inputs and invariant to any permutations of n coordinates. Then, for sufficiently Under review as a conference paper at ICLR 2020 small ε > 0, we obtain

R(f Sn ) ≤ R m (f Sn ) + C n! mε p + O(log(1/ε))

, with probability at least 1 -O(ε). Here, C > 0 is a constant independent of m and n.

As a consequence of Theorem 1, the generalization bound is improved by

√:

n! by the invariant property. Since the number of coordinates n is huge in practice, e.g. there are n ≥ 1, 000 points in the point cloud data in Zaheer et al. (2017) and hence

n! ≥ 10 1,000 holds, we show that the derived generalization bound is largely improved by invariance. Further, we also derive a rate of approximation of neural networks with invariance (Theorem 4) and its optimality, thus we show that an invariance property for deep neural networks does not reduce an expressive power.

From a technical aspect, we develop mainly three proof technique to obtain the improved bound in Theorem 1. Firstly, we introduce a notion of a fundamental domain to handle invariance of functions and evaluate the complexity of the domain (Lemma 1). Secondly, we show a one-to-one correspondence between a function by invariant deep neural networks and a function on the fundamental domain (Proposition 2). Thirdly, we develop a scale-sensitive covering number to control a volume of invariant functions with neural networks (Proposition 5). Based on the techniques, we can connect a generalization analysis to the invariance of deep neural networks.

We summarize the contributions of this paper as follow:

• We investigate the generalization bound of deep neural networks which are invariant to permutation of n coordinates, then we show that the bound is improved by

√ n!.

• We derive a rate of approximation of invariant deep neural networks. The result shows that the approximation rate is optimal. • We develop several proof techniques to achieve the bound such as a complexity analysis for a fundamental domain and a scale-sensitive metric entropy. 

q := ( D j=d b q d ) 1/q is the q-norm for q ∈ [0, ∞]. For a tensor A ∈ R D1×D2 , a (d 1 , d 2 )-th element of A is written as A d1,d2

. For a function f : Ω → R with a set Ω, f L q := ( Ω |f (x)| q dx) 1/q denotes the L q -norm for q ∈ [0, ∞]. For a subset Λ ⊂ Ω, f Λ denotes the restriction of f to Λ. For an integer z, z! = n j=1 j denotes a factorial of z. For a set Ω with a norm • , N (ε, Ω, • ) := inf{N : ∃{ω j } N j=1 s.t. ∪ N j=1 {ω : ω -ω j ≤ ε} ⊃ Ω} is a covering number of Ω with ε > 0. For a set Ω, id Ω or id denotes the identity map on Ω, namely id Ω (x) = x for any x ∈ Ω. For a subset ∆ ⊂ R n , int(∆) denotes the set of the inner points of ∆.

2. PROBLEM SETTING:



2.1. INVARIANT DEEP NEURAL NETWORK:

We define a set of permutation S n in this paper. Consider x ∈ R n×D where n be a number of coordinates in x and D be a dimension of each coordinate. Then, an action σ ∈ S n on x is defined as

(σ • x) i,d = x σ -1 (i),d , i = 1, ..., n, d = 1, ..., D,

here, σ is a permutation of indexes i. Also, we define an invariant property for general functions. Definition 1 (S n -Invariant/Equivariant Function). For a set X ⊂ R n×D , we say that a map f :

X → R M is • S n -invariant (or simply invariant) if f (σ • x) = f (x)

for any σ ∈ S n and any x ∈ X ,

• S n -equivariant (or simply equivariant) if there is an S n -action on R M and f (σ

• x) = σ • f (x)

for any σ ∈ S n and any x ∈ X .

In this paper, we mainly treat fully connected deep neural networks with a ReLU activation function.

The ReLU activation function is defined by ReLU(x) = max(0, x). Deep neural networks are built by stacking blocks which consist of a linear map and a ReLU activation. More formally, it is a function

Z i : R di → R di+1 defined by Z i (x) = ReLU(W i x + b i ), where W i ∈ R di+1×di and b i ∈ R di+1 for i = 1, ..., H.

Here, H is a depth of the deep neural network and d i is a width of the i-th layer. An output of deep neural networks is formulated as

EQUATION

Let F DN N be a set of functions by deep neural networks.

We also consider an invariant deep neural network defined as follows:

Definition 2 (Invariant Deep Neural Network). f ∈ F DN N is a function by a S n -invariant deep neural network, if f is a S n -invariant function. Let F Sn DN N ⊂ F DN N be a set of functions by S n -invariant deep neural networks.

The definition is a general notion and it contains several explicit invariant deep neural networks. We provide several representative examples as follow.

Example 1 (Deep Sets). Zaheer et al. (2017) develops an architecture for invariant deep neural networks by utilizing layer-wise equivariance. Their architecture consists of equivariant layers 1 , ..., j , an invariant linear layer h, and a fully-connected layer f . For each i .i = 1, .., j, its parameter matrix is defined as

W i = λI + γ(11 ), λ, γ ∈ R, 1 = [1, ..., 1] ,

which makes i as a layer-wise equivariant function.

They show that f = f • h • j • • • • 1 is an invariant function. Its illustration is provided in Figure 1.

Example 2 (Invariant Feature Extraction). Let e is a mapping for invariant feature extraction which will be explicitly constructed by deep neural networks in Proposition 2. Then, a function f = g • e where g is a function by deep neural networks with a restricted domain. Figure 2 provides its image.

2.2. LEARNING PROBLEM WITH INVARIANT NETWORK:

Problem formulation: Let I = [0, 1] n×D be an input space with dimension p = dD. Let Y be an output space. Also, let L : Y × Y → R be a loss function which satisfies sup y,y ∈Y |L(y, y )| ≤ 1 and 1-Lipschitz continuous. Let P * (x, y) be the true unknown distribution on I ×Y, and for f :

I → Y, R(f ) = E (X,Y )∼P * [L(f * (X), Y )]

be the expected risk of f . Also, suppose we observe a training dataset

D m := {(X 1 , Y 1 ), ..., (X m , Y m )} of size m. Let R m (f ) := m -1 m i=1 L(f (X i ), Y i )

be the empirical risk of f . A goal of this study to investigate the expected loss R(f ) with a function f from a set of functions as a hypothesis set.

Learning with Invariant Network: We consider learning with a hypothesis set by invariant deep networks. Namely, we fix an architecture of deep neural networks preserves f Sn ∈ F Sn DN N to be an invariant function. Then, we evaluate the expected loss R(f Sn ). is an equivariant layer, h is a linear invariant layer, and f is a function by networks. 

3. MAIN RESULT:



3.1. COMPLEXITY-CONTROL BOUND:

We show that the learning procedure with invariance can largely improve the generalization performance of a deep neural network by proving the improved bound for the generalization error of f with invariance. We firstly derive a Complexity-dependent bound which holds with an arbitrary true distribution. The bound depends on a Complexity control of F Sn DN N and the Rademacher complexity.

Theorem 2 (Main Result 1). Let F Sn DN N be a set of functions by S n -invariant deep neural networks which are C ∆ -Lipschitz continuous and bounded by B > 0. Then, for any f Sn ∈ F Sn DN N and for any ε > 0, the following inequality holds with probability at least 1 -2C ∆ ε:

R(f Sn ) ≤ R m (f Sn ) + 2c 1 n! mε p =:I1 + 2 log(2c 2 B/ε) + 2 log(1/2ε) m =:I2

, where c 1 , c 2 > 0 are constants which are independent of n and m.

Significantly, the main term I 1 in Theorem 2 is improved by √ n! in the denominator. Note that we regard I 1 as the main term since I 2 is a logarithmic order in ε. As n is huge in practice, e.g. a number of points in point cloud data, the term n! largely improves the tightness of the bound.

We mention that ε p appears in the denominator of I 1 and it looks a harmful term when p = nD is large. However, the term is negligible with large n, because n! increases much faster than ε nD . Namely, we can obtain n!ε nD = Ω(n c ) holds for any c > 0 and ε > 0 as n → ∞.

Proof of Theorem 2 utilizes a complexity control for F Sn DN N . As a preparation, we apply the wellknown bound (e.g. a slightly modified version of Theorem 10.1 in Anthony & Bartlett (2009) ) and obtain

EQUATION

which describes generalization of f Sn by the covering number log 2N (ε, F Sn DN N , • L ∞ ). Then, we bound the covering number by the following Theorem which plays a key role to achieve the main result in Theorem 2. Proof of Theorem 3 depends on several newly developed results presented in Section 4. Theorem 3 (Complexity Bound). Let F Sn DN N be defined in section 2. Then, with an existing constant c > 0, we obtain

log N (2C ∆ δ, F Sn DN N , • L ∞ (I) ) ≤ c n! δ p + log 2cB δ .

Remark 1 (Bound without invariance). The bound is a general version of an ordinary learning f ∈ F DN N which does not have invariance. Rigorously, suppose F DN N is a set of functions which are C ∆ -Lipschitz continuous and bounded by B > 0. Then, for any f ∈ F DN N and ε > 0, the inequality in Theorem 2 holds with n = 1. Remark 2 (Bound for covering numbers). We mention that there is another way to bound the covering number of F Sn DN N by a number of parameters (e.g. Theorem 14.5 in Anthony & Bartlett (2009) ). Such a bound has a fast order since its order is a logarithm of ε. However, the bound has a linear order in a number of parameters, hence it easily increases with large-scale deep neural networks which possess a huge number of nodes and edges. Moreover, such a bound is independent of the volume of the domain, hence we cannot obtain the scale-sensitive covering number. To avoid the problem, we employ another strategy in Theorem 3.

3.2. APPROXIMATION-CONTROL BOUND:

We investigate the approximation power of invariant deep neural networks to clarify how they can achieve a small empirical loss. Although we restrict the expressive power of deep neural networks in the learning procedure, we prove that our networks have sufficient power of approximation. To the aim, we define the Hölder space which is a class of smooth functions, then investigate the approximation power of invariant deep neural networks for the space. Definition 3 (Hölder space). Let α > 0 be a degree of smoothness. For f : I → R, the Hölder norm is defined as

f H α := max β:|β|< α sup x∈I |∂ β f (x)| + max β= α sup x,x ∈I,x =x |∂ β f (x) -∂ β f (x )| x -x α-α ∞ .

Then, the Hölder space on I is defined as

H α = f ∈ C α f H α < ∞ . Also, H α B = {f ∈ H α | f H α ≤ B} denotes the B-radius closed ball in H α .

Intuitively, H α is a set of bounded functions which are α-times differentiable. The notion of the Hölder space is often utilized in characterizing the optimal functions f * (e.g. see Schmidt-Hieber ( 2017)). We achieve the more detailed bound for the generalization error with assuming f * ∈ H α B . Theorem 4 (Main Theorem 2). For any ε > 0, suppose F Sn DN N has at most O(log(1/ε))layers and O(ε -p/α log(1/ε)) non-zero parameters. Then, for any invariant

f * ∈ H α B , there is f Sn ∈ F Sn DN N such that f Sn -f * L ∞ (I) ≤ ε.

The result in Theorem 4 clarifies the approximation power of deep networks, and also show that a sufficient number of parameters (nodes) makes the generalization error converge to zero. Also, the theorem shows that the approximation error decreases as the number of parameters increase with the rate -p/α up to log factors. The rate is the optimal rate by Yarotsky (2017) without invariance. Hence, we prove that the deep networks with invariance can achieve the optimal approximation rate even with the invariance restriction.

4. PROOF AND ITS STRATEGY:



4.1. FUNDAMENTAL DOMAIN AND ITS CORRESPONDENCE:

To handle the invariance property in our proof, we provide a key notion to show the main result. Definition 4 (Fundamental Domain). Let G be a group acting on a set J. ∆ ⊂ J is said to be a fundamental domain of J with respect to the action of G if ∆ satisfy the following properties;

• J = ∪ σ∈G {σ • x | x ∈ ∆}. • σ • int(∆) ∩ τ • int(∆) = ∅ for any σ = τ ∈ G.

In our case, we can take a fundamental domain explicitly. Proposition 1. Put I = [0, 1] n×D . Then

∆ := {x ∈ I | x 1,1 ≥ x 2,1 ≥ • • • ≥ x n,1 }

is a fundamental domain of I with respect to the permutation action of S n defined in Section 2.1.

Figure 3 provides ∆ with n = 3 and D = 1. Intuitively, ∆ is an extracted feature space for an invariant function. Any element of I corresponds to an element of ∆ with an existing action in S n , namely, we can obtain

I = ∪ σ∈Sn {σ • x | x ∈ ∆} .

Proof of Proposition 1. We confirm the first property of the fundamental domain, namely implies the first property. We confirm the second property. We have int

I = ∪ σ∈G {σ • x | x ∈ ∆}. Take x ∈ I. There is a σ -1 ∈ S n such that x σ(1),1 ≥ x σ(2),1 ≥ • • • ≥ x σ(n),1 . Then by the definition of ∆, σ -1 • x ∈ ∆. Hence x ∈ σ • ∆ = {σ • x | x ∈ ∆} . This

(∆) = {x ∈ I | x 1,1 > x 2,1 > • • • > x n,1 } By the definition of our action, σ • int(∆) = x ∈ I | x σ -1 (1),1 > x σ -1 (2),1 > • • • > x σ -1 (n),1 . Hence σ • int(∆) ∩ τ • int(∆) = ∅ for any σ = τ ∈ G.

We provide two important properties of ∆. Firstly, we start with showing that there is a one-to-one correspondence between deep neural networks on ∆ and invariant deep neural networks on I. To the aim, we consider a set of functions on ∆ by (not necessarily invariant) deep neural networks;

F ∆ DN N = {g : ∆ → R | g has the form (1)}.

Then, we obtain the following result::

Proposition 2. There exists a bijection map Λ : F Sn DN N → F ∆ DN N . Further, for any f ∈ F Sn DN N , Λ(f ) is obtained by the restriction of f , namely Λ(f ) = f ∆ , and for any g ∈ F ∆ DN N , Λ -1 (g) can be obtained by adding sorting layers appeared in the proof.

Figure 4 provides an image for Λ -1 (g) for g ∈ F ∆ DN N . For preparation for proof of Proposition 2, we define an explicit invariant deep neural network. For a vector z ∈ R N for some N , let max (j) (z 1 , . . . , z N ) (resp. min (j) (z 1 , . . . , z N )) be a function which returns the j-th largest (resp. smallest) element of {z 1 , . . . , z N }. We can easily see that these functions are a S n -invariant function. More strongly, we have the following proposition.

Proposition 3. max (j) (z 1 , . . . , z N ) and min (j) (z 1 , . . . , z N ) are represented by an existing deep neural networks with an ReLU activation for any j = 1, ..., N .

Proof of Proposition 3. Firstly, since

max(z 1 , z 2 ) = max(z 1 -z 2 , 0) + z 2 , and min(z 1 , z 2 ) = -max(z 1 -z 2 , 0) + z 1

hold, we see the case of j = 1, N = 2. By repeating max(z 1 , z 2 ), we construct max (1) (z 1 , . . . , z N ) and min (1) (z 1 , . . . , z N ). Namely, we prove the claim in the case of j = 1 and arbitrary N . At first, we assume N is even without loss of generality, then we divide the set {z 1 , ...z N } into sets of pairs {(z 1 , z 2 ), ...(z N -1 , z N )}. Then, by taking a max operation for each of the pairs, we have {y 1 = max(z 1 , z 2 ), ..., y N/2 = max(z N -1 , z N )} . We repeat this process to terminate. Then we have max (1) (z 1 , . . . , z N ) it is represented by an existing deep neural network. Similarly, we have min (1) (z 1 , . . . , z N ). Finally, we prove the claim on j = 2, ..., N by induction. Assume that for any N and < j, max ( ) (z 1 , . . . , z N ) is represented by a deep neural network. We construct max (j) (z 1 , . . . , z N ) as follows: since

max (j-1) (z -) = max (j-1) (z 1 , . . . , z N ) (if z ≤ max (j) (z 1 , . . . , z N )) max (j) (z 1 , . . . , z N ) (otherwise)

holds, we have max (j) (z 1 , . . . , z N ) = min({max (j-1) (Z ) | = 1, ..., N }). By inductive hypothesis, the right hand side is represented by a deep neural network.

Proof of Proposition 2. We first define sorting layers which is an S n -invariant network mapping from I to ∆.When D = 1, put Sort 1 (x 1,1 , . . . , x n,1 ) = (max (1) (x 1,1 , . . . , x n,1 ), . . . , max (n) (x 1,1 , . . . , x n,1 )).

Then by Proposition 3, Sort 1 (x 1,1 , . . . , x n,1 ) = Sort 1 (x 1,1 , . . . , x n,1 ) is also a function by an S n -invariant deep neural network and Sort(x 1,1 , . . . , x n,1 ) is the function from I to ∆. When D > 1, we first consider Sort 1 (x 1,1 , . . . , x n,1 ). Since Sort 1 (x 1,1 , . . . , x n,1 ) gives a permutation on (x 1,1 , . . . , x n,1 ), for each (x 1,1 , . . . , x n,1 ), we can find σ ∈ S n such that Sort 1 (x 1,1 , . . . , x n,1 ) = (Sort 1 (x 1,1 , . . . , x n,1 ) 1 , ..., Sort 1 (x 1,1 , . . . , x n,1 ) n ) = (x σ(1),1 , . . . , x σ(n),1 ).

Then we define:

Sort(x) =        Sort 1 (x 1,1 , . . . , x n,1 ) 1 • • • x σ(1),d • • • x σ(1),D . . . . . . . . . Sort 1 (x 1,1 , . . . , x n,1 ) i x σ(i),d x σ(i),D . . . . . . . . . Sort 1 (x 1,1 , . . . , x n,1 ) n • • • x σ(n),d • • • x σ(n),D       

.

By the construction and the definition of ∆, Sort(x) is the function to ∆. We confirm Sort(x) is S n -invariant. Take arbitrary τ ∈ S n and fix x and σ ∈ S n as above. Put τ • x = y. We show Sort(y) = Sort(x). Since Sort 1 is an S n -invariant function, we see Sort

1 (y 1,1 , . . . , y n,1 ) = Sort 1 (τ (x 1,1 , . . . , x n,1 )) = (x σ(1),1 , . . . , x σ(n),1 ) = (y σ(τ -1 (1)),1 , . . . , y σ(τ -1 (n)),1

). Then we have

Sort(y) =        Sort 1 (y 1,1 , . . . , y n,1 ) 1 • • • y σ(τ -1 (1)),d • • • y σ(τ -1 (1)),D . . . . . . . . . Sort 1 (y 1,1 , . . . , y n,1 ) i y σ(τ -1 (i)),d y σ(τ -1 (i)),D . . . . . . . . . Sort 1 (y 1,1 , . . . , y n,1 ) n • • • y σ(τ -1 (n)),d • • • y σ(τ -1 (n)),D        =        Sort 1 (x 1,1 , . . . , x n,1 ) 1 • • • x σ(1),d • • • x σ(1),D . . . . . . . . . Sort 1 (x 1,1 , . . . , x n,1 ) i x σ(i),d x σ(i),D . . . . . . . . . Sort 1 (x 1,1 , . . . , x n,1 ) n • • • x σ(n),d • • • x σ(n),D        = Sort(x),

where the second equality follows from τ -1 • y = x. By using this function, we define the inverse of Λ. For any function f by a deep neural network on ∆, we define

Φ(f ) = f • Sort. We confirm Λ • Φ = id F∆ and Φ • Λ = id F Sn . Since we have Λ • Φ(f ) = Λ • f • Sort = (f • Sort) ∆ = f, Λ • Φ is equal to id F∆ . Similarly, Φ • Λ(f ) = Φ • f ∆ = f ∆ • Sort = f,

where the last equality follows from the S n -invariance of f . Hence, we have the desired result.

The second key property of ∆ is that we can measure its size. Since ∆ is included in I, we can naturally measure its volume by the Euclidean metric. By utilizing the property, we evaluate its volume by a covering number of ∆ by the following lemma: Lemma 1 (Covering bound for ∆). There is a constant C such that for enough small ε > 0, we obtain

N (ε, ∆, • ∞ ) ≤ C n! ε nD .

Proof of Lemma 1. Let C(I) be a set of ε-cubes which is a standard subdivision of I. We can easily see that C(I) attains the minimum value ε -nD of the number of ε-cubes which is the covering of I.

We show that we can find a subset of C(I) whose cardinality is ε -nD n! + O(ε -n(D-1) ). The strategy of the proof is as follows. At first, we calculate the number A of cubes in C(I) which intersect with the boundary of σ • ∆. Then since the permutation on the cubes which do not intersect with the boundary of σ •∆ is free, if A is O(ε -n(D-1) ), we can find the covering whose cardinality is ε

-nD n! + O(ε -n(D-1) ). Since σ • ∆ is x ∈ I | x σ -1 (1),1 ≥ x σ -1 (2),1 ≥ • • • ≥ x σ -1 (n),1 , any boundary of σ • ∆ is of the form x ∈ I | x σ -1 (1),1 ≥ • • • x σ -1 (i),1 = x σ -1 (i+1),1 ≥ • • • ≥ x σ -1 (n),1 .

Fix σ and i. Consider the projection π : R n×D → R n-1×D which sends x σ -1 (i),1 to zero. π induces the map π : C(I) → C(π(I)), where C(π(I)) is a set of -cubes which is the subdivision of π(I) induced by C(I) . Let C(I) diag denote the set of cubes in C(I) which intersect with the set B = x ∈ I | x σ -1 (i),1 = x σ -1 (i+1),1 . Then we can see that π is injective on C(I) diag as follows.

Let us denote a = (a s,r ) ∈ R nD the center of an ε-cube in C(I). Assume that there are two cubes in C(I) diag whose images by π are equal. Let us denote the centers of two cubes by a and a .Then we have π(a) = π(a ) and hence a s,r = a s,r holds for (s, r) = (σ -1 (i), 1). Here, by our construction of ε-cubes, a cube (in C(I)) intersect with B if and only if its center is on B . Therefore, since two cubes are in C(I) diag , we have a σ -1 (i),1 = a σ -1 (i+1),1 and a σ -1 (i),1 = a σ -1 (i+1),1 . Hence a s,r = a s,r holds for any (s, r) and two cubes are equal and π is injective on C(I).

Next, let C (I) be the set of ε-cubes in C(I) which intersect a boundary of σ • ∆. We see that the cardinality of C (I) is bounded by Eε -n(D-1) for some E. Since the number of components of the boundaries is finite, we prove the claim for a component of the boundary. Since p C(I) diag is injective, we see the number of cubes which intersect the component is bounded by the number of ε-cubes in C(p(I)), hence ε -n(D-1) . Put C(I) inn = C(I) -C (I). Then each cubes in C(I) inn does not intersect the boundaries of σ • ∆. Hence, there is a σ such that the number of cubes C(I) inn which are contained in σ • ∆ is lower than |C(I)inn| n!

. By adding the cubes which cover the boundaries of σ • ∆, we have the covering of σ • ∆. Furthermore, by pulling back by σ , we have the covering of ∆. Hence, we have -1) .

N (ε, ∆, • ∞ ) ≤ |C(I)| -Eε -n(D-1) n! + E ε -n(D

Since |C(I)| = ε -nD , we have the desired result.

4.2. PROOF FOR THE COMPLEXITY-CONTROL BOUND (THEOREM 2):

We utilize the results of ∆ and prove Theorem 2. The proof mainly contains the following two-step: i) show that the covering number of F Sn DN N is equal to that of F ∆ DN N , and ii) bound the covering number of F ∆ DN N . The first step is provided by the following proposition. Proposition 4. For any ε > 0, we obtain

log N (ε, F Sn DN N , • L ∞ (I) ) = log N (ε, F ∆ DN N , • L ∞ (I) ).

The result shows that the functional set by deep neural networks on I with invariance is well described by a set of functions on ∆ without invariance. The key point of this result is that we can describe the effect of invariance restriction on F Sn DN N by the size of F ∆ DN N .

Proof of Proposition 4. For any f, f ∈ F Sn DN N , there exists f ∆ , f ∆ ∈ F ∆ by Proposition 2. Then, we can obtain

f -f L ∞ (I) = f ∆ • g -f ∆ • g L ∞ (I) ≤ f ∆ -f ∆ L ∞ (∆) .

Based on the result, we can bound log N (ε,

F Sn DN N , • L ∞ (I) ) by log N (ε, F ∆ , • L ∞ (∆) ). Suppose log N (ε, F ∆ , • L ∞ (∆) ) =: K is finite.

Then, there exist f ∆ 1 , ..., f ∆ K , and for any f ∆ ∈ F ∆ , there exists j ∈ {1, ..., K} such as f ∆ -f ∆j L ∞ (∆) ≤ ε. Here, for any f ∈ F Sn DN N , there exists

f j := f ∆ j • g ∈ F Sn DN N with corresponding j and it satisfies f -f j L ∞ (I) ≤ f ∆ -f ∆j L ∞ (∆) ≤ ε.

Then, we obtain the statement.

where g • Sort is a neural network with at most O(log(N )) + K 1 layers and at most O(N log(N )) + K 2 nonzero weights, where K 1 and K 2 are the number of layers and the number of nonzero weights of the neural network expressing Sort respectively. By replacing N -1 with ε, we have the desired inequality.

5. DISCUSSION AND COMPARISON:

We discuss the technical non-triviality of our result. One can consider that our result seems straightforward, because the improvement by

n! looks a kind of folklore. However, there are several technical difficulties to prove it. Rigorously speaking, to obtain the improved bound, we have to find n! subsets of functions without overlapping with each other. To find them, we introduce the notion of the fundamental domain (Definition 4) and prove that a volume of overlapping of the subsets has measure zero (Lemma 1). To the best of knowledge, this is the first study to show the result.

We mention that Sokolic et al. (2016) investigates a generalization bound for classification with invariant algorithms. Scope of the study is not limited to deep neural networks, but a wide class of learning problems. The generalization bound by the study is improved by

T , where T is a number of possible transformations for invariance. To discriminate this paper from the study by Sokolic et al. (2016) , we provide several differences between the study and this paper. Firstly, we construct an explicit framework for invariant deep neural networks, which guarantees the practical usage of several methods. Especially, the framework contains the famous network as the DeepSets by Zaheer et al. (2017) . Hence, our paper can provide useful knowledge for practical use, while the study by Sokolic et al. (2016) investigates an abstract problem. Secondly, our analysis is not limited to classifications, but can be applied to general learning methods including regression. Thirdly, we focus on the more specific permutation invariance, and obtain the explicit improvement of the generalization bound. The bound by Sokolic et al. (2016) considers a more abstract problem with a wide class of invariance, hence it is not clear to obtain the same generalization bound of this paper.

6. CONCLUSION:

In this paper, we develop a generalization theory to clarify the higher precision of the invariant deep neural network. Our generalization bound shows that it gets much tight by the invariant property, rigorously, the bound is improved by

n! where n is a number of permutation-invariant coordinates. Intuitively, this is caused by fact that the input space is divided into n! copies of subspace which can be moved by permutation to each other. We further prove that the invariant deep neural network with a ReLU activation can achieve the optimal approximation rate for smooth functions. By the results, our theory shows a great advantage of deep neural networks.

As an improvement of our result, it is an open question to connect the invariant property and the norm-controlled entropy control for deep neural networks (e.g. the work by Bartlett et al. (2017) ). To describe the practical high accuracy of deep learning, numerous studies investigigate the the norm-controlled entropy. We guess that our theory is valid with the entropy and more suitable to analyze the performance of invariant deep neural networks.

:



Figures and Tables:

b ∈ R D , its d-th element is denoted by b d . Also, b -d := (b 1 , ..., b d-1 , b d+1 , ..., b D ) ∈ R D-1 is a vector without b d . b

Figure 1: The invariant deep neural network by DeepSets (Zaheer et al. (2017)).is an equivariant layer, h is a linear invariant layer, and f is a function by networks.

Figure 2: The invariant deep neural network by a fully connected layer g and a feature extraction layer e.

Figure 3: A fundamental domain ∆ (the green cone) in I (the blue cube) with n = 3 and D = 1.

Figure 4: The Sort layer (red) which converts g ∈ F ∆ DN N to f = Λ -1 (g) ∈ F Sn DN N with n = D = 3. The Sort layer exchanges the first elements of each x i ∈ R D .

Peer review (iclr2020):
This paper derives a generalization bound for permutation invariant networks. The main idea is to prove that the bound is inversely proportional to the square-root of the number of possible permutations to the input. The key result is Theorem 3 that bounds the covering number of a neural network (defined under an approximation control bound, Thm 4) using the number of permutations. The paper proves the theorem by showing that the space of input permutations can reduced to group actions over a fundamental domain, and deriving a bound for the covering number of the fundamental domain (Lemma 1), which is then extended to derive the same for the neural network setting. For the permutation invariance setting, the fundamental domain is obtained via the sorting operator. Pros: 1. The paper appears to be mathematically rigorous, and at the same time, is straightforward to follow, with useful intuitions provided whenever required. 2. The provided theoretical result perhaps extends the work on universal approximation theorem for permutation invariant networks in Sennai et al, and Maron et al., 2019. Further, the generalization bound for permutation invariance is new to my knowledge. Cons: 1. While, the proof appears to be novel for permutation invariance per se, however I do not think the main findings in this paper or the proof approach are sufficiently novel. For example, generalization bounds under invariances have been explored previously, perhaps the most related to this paper is [a] below that already shows (in a similar vein as this paper) that the bound decreases proportional to 1/sqrt(T), where T is the number of invariances used. While, that work uses affine transformations of the input from a base space for the invariances (which this paper calls fundamental domain), the current paper uses permutation invariance and thus gets the bound proportional to 1/sqrt(n!). In the context of this prior work, the contribution of this paper appears incremental. The paper should cite this work and contrast against the results and proof methods in it. [a] Generalization Error of Invariant Classifiers, Sokolic et al., ICML 2017. 2. The paper has several typos and grammatical errors through out, which are easily fixable though! Overall, this paper is technically rigorous, and novel in its very specific context of deriving the generalization bounds for permutation invariant networks. However, in the broader context of invariances in general and their bounds, the contribution appears to be marginal.