Year: 2019

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.

text: √ 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.

heading: 1 INTRODUCTION
text: 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 (Xi, Yi) where Xi are regarded as pdimensional vectors, and Xi can divided to n coordinates and each of them have D = p/n dimension. Also, let fSn denote a function by a deep neural network which satisfies an invariant property, f(x) = f(σ · x) holds for any x ∈ Rn×D where σ is an arbitrary permutation of D-dimensional coordinates in x. Also, we define Rm(f) = m−1 ∑m i=1 L(Yi, f(Xi)) 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 fSn be a function by a deep neural network which takes p-dimensional inputs and invariant to any permutations of n coordinates. Then, for sufficiently
small ε > 0, we obtain R(fSn) ≤ Rm(fSn) + √ 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! ≥ 101,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.

heading: 1.1 NOTATION
text: For a vector b ∈ RD, its d-th element is denoted by bd. Also, b−d := (b1, ..., bd−1, bd+1, ..., bD) ∈ RD−1 is a vector without bd. ‖b‖q := ( ∑D j=d b q d)
1/q is the q-norm for q ∈ [0,∞]. For a tensor A ∈ RD1×D2 , a (d1, d2)-th element of A is written as Ad1,d2 . For a function f : Ω → R with a set Ω, ‖f‖Lq := ( ∫ Ω |f(x)|qdx)1/q denotes the Lq-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}Nj=1 s.t. ∪Nj=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 ∆ ⊂ Rn, int(∆) denotes the set of the inner points of ∆.

heading: 2 PROBLEM SETTING

heading: 2.1 INVARIANT DEEP NEURAL NETWORK
text: We define a set of permutation Sn in this paper. Consider x ∈ Rn×D where n be a number of coordinates in x and D be a dimension of each coordinate. Then, an action σ ∈ Sn 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 (Sn-Invariant/Equivariant Function). For a set X ⊂ Rn×D, we say that a map f : X → RM is
• Sn-invariant (or simply invariant) if f(σ · x) = f(x) for any σ ∈ Sn and any x ∈ X ,
• Sn-equivariant (or simply equivariant) if there is an Sn-action on RM and f(σ · x) = σ · f(x) for any σ ∈ Sn 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 Zi : Rdi → Rdi+1 defined by Zi(x) = ReLU(Wix + bi), where Wi ∈ Rdi+1×di and bi ∈ Rdi+1 for i = 1, ...,H . Here, H is a depth of the deep neural network and di is a width of the i-th layer. An output of deep neural networks is formulated as
f(x) := ZH ◦ ZH−1 . . . Z2 ◦ Z1(x). (1)
Let FDNN 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 ∈ FDNN is a function by a Sn-invariant deep neural network, if f is a Sn-invariant function. Let FSnDNN ⊂ FDNN be a set of functions by Sn-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
Wi = λ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.

heading: 2.2 LEARNING PROBLEM WITH INVARIANT NETWORK
text: 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 supy,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 datasetDm := {(X1, Y1), ..., (Xm, Ym)} of sizem. LetRm(f) := m−1 ∑m i=1 L(f(Xi), Yi) be the empirical risk of f . A goal of this study to investigate the expected lossR(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 fSn ∈ FSnDNN to be an invariant function. Then, we evaluate the expected loss R(fSn).

heading: 3 MAIN RESULT

heading: 3.1 COMPLEXITY-CONTROL BOUND
text: 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 FSnDNN and the Rademacher complexity.
Theorem 2 (Main Result 1). Let FSnDNN be a set of functions by Sn-invariant deep neural networks which are C∆-Lipschitz continuous and bounded by B > 0. Then, for any fSn ∈ FSnDNN and for any ε > 0, the following inequality holds with probability at least 1− 2C∆ε:
R(fSn) ≤ Rm(fSn) + √
2c1 n! mεp︸ ︷︷ ︸ =:I1 +
√ 2 log(2c2B/ε) + 2 log(1/2ε) m︸ ︷︷ ︸ =:I2 ,
where c1, c2 > 0 are constants which are independent of n and m. Significantly, the main term I1 in Theorem 2 is improved by √ n! in the denominator. Note that we regard I1 as the main term since I2 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 I1 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 = Ω(nc) holds for any c > 0 and ε > 0 as n→∞.
Proof of Theorem 2 utilizes a complexity control for FSnDNN . As a preparation, we apply the wellknown bound (e.g. a slightly modified version of Theorem 10.1 in Anthony & Bartlett (2009)) and obtain
R(fSn) ≤ Rm(fSn) +
√ 2 log 2N (ε,FSnDNN , ‖ · ‖L∞) + 2 log(1/2ε)
m , (2)
which describes generalization of fSn by the covering number log 2N (ε,FSnDNN , ‖ · ‖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). LetFSnDNN be defined in section 2. Then, with an existing constant c > 0, we obtain
logN (2C∆δ,FSnDNN , ‖ · ‖L∞(I)) ≤ c
n! δp + log
( 2cB
δ
) .
Remark 1 (Bound without invariance). The bound is a general version of an ordinary learning f ∈ FDNN which does not have invariance. Rigorously, suppose FDNN is a set of functions which are C∆-Lipschitz continuous and bounded by B > 0. Then, for any f ∈ FDNN 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 FSnDNN 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.

heading: 3.2 APPROXIMATION-CONTROL BOUND
text: 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 Hölder space which is a class of smooth functions, then investigate the approximation power of invariant deep neural networks for the space. Definition 3 (Hölder space). Let α > 0 be a degree of smoothness. For f : I → R, the Hölder norm is defined as
‖f‖Hα := max β:|β|<bαc sup x∈I |∂βf(x)|+ max β=bαc sup x,x′∈I,x6=x′ |∂βf(x)− ∂βf(x′)| ‖x− x′‖α−bαc∞ .
Then, the Hölder space on I is defined as Hα = { f ∈ Cbαc ∣∣∣‖f‖Hα <∞} . Also,HαB = {f ∈ Hα | ‖f‖Hα ≤ B} denotes the B-radius closed ball inHα.
Intuitively, Hα is a set of bounded functions which are α-times differentiable. The notion of the Hö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 FSnDNN has at most O(log(1/ε))layers and O(ε−p/α log(1/ε)) non-zero parameters. Then, for any invariant f∗ ∈ HαB , there is fSn ∈ F Sn DNN such that
‖fSn − 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.

heading: 4 PROOF AND ITS STRATEGY

heading: 4.1 FUNDAMENTAL DOMAIN AND ITS CORRESPONDENCE
text: 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 σ 6= τ ∈ G.
In our case, we can take a fundamental domain explicitly. Proposition 1. Put I = [0, 1]n×D. Then
∆ := {x ∈ I | x1,1 ≥ x2,1 ≥ · · · ≥ xn,1}
is a fundamental domain of I with respect to the permutation action of Sn 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 Sn, namely, we can obtain
I = ∪σ∈Sn {σ · x | x ∈ ∆} .
Proof of Proposition 1. We confirm the first property of the fundamental domain, namely I = ∪σ∈G {σ · x | x ∈ ∆}. Take x ∈ I . There is a σ−1 ∈ Sn such that xσ(1),1 ≥ xσ(2),1 ≥ · · · ≥ xσ(n),1. Then by the definition of ∆, σ−1 · x ∈ ∆. Hence x ∈ σ · ∆ = {σ · x | x ∈ ∆} . This
implies the first property. We confirm the second property. We have int(∆) = {x ∈ I | x1,1 > x2,1 > · · · > xn,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 σ 6= τ ∈ 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∆DNN = {g : ∆→ R | g has the form (1)}.
Then, we obtain the following result:
Proposition 2. There exists a bijection map Λ : FSnDNN → F∆DNN . Further, for any f ∈ F Sn DNN , Λ(f) is obtained by the restriction of f , namely Λ(f) = f ∆ , and for any g ∈ F∆DNN , Λ−1(g) can be obtained by adding sorting layers appeared in the proof.
Figure 4 provides an image for Λ−1(g) for g ∈ F∆DNN . For preparation for proof of Proposition 2, we define an explicit invariant deep neural network. For a vector z ∈ RN for some N , let max(j)(z1, . . . , zN ) (resp. min(j)(z1, . . . , zN )) be a function which returns the j-th largest (resp. smallest) element of {z1, . . . , zN}. We can easily see that these functions are a Sn-invariant function. More strongly, we have the following proposition.
Proposition 3. max(j)(z1, . . . , zN ) and min(j)(z1, . . . , zN ) are represented by an existing deep neural networks with an ReLU activation for any j = 1, ..., N .
Proof of Proposition 3. Firstly, since
max(z1, z2) = max(z1 − z2, 0) + z2, and min(z1, z2) = −max(z1 − z2, 0) + z1
hold, we see the case of j = 1, N = 2. By repeating max(z1, z2), we construct max(1)(z1, . . . , zN ) and min(1)(z1, . . . , zN ). 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 {z1, ...zN} into sets of pairs {(z1, z2), ...(zN−1, zN )}. Then, by taking a max operation for each of the pairs, we have {y1 = max(z1, z2), ..., yN/2 = max(zN−1, zN )} . We repeat this process to terminate. Then we have max(1)(z1, . . . , zN ) it is represented by an existing deep neural network. Similarly, we have min(1)(z1, . . . , zN ). Finally, we prove the claim on j = 2, ..., N by induction. Assume that for any N and ` < j, max(`)(z1, . . . , zN ) is represented by a deep neural network. We construct max(j)(z1, . . . , zN ) as follows: since
max(j−1)(z−`) = { max(j−1)(z1, . . . , zN ) (if z` ≤ max(j)(z1, . . . , zN )) max(j)(z1, . . . , zN ) (otherwise)
holds, we have max(j)(z1, . . . , zN ) = 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 Sn-invariant network mapping from I to ∆.When D = 1, put Sort1(x1,1, . . . , xn,1) = (max(1)(x1,1, . . . , xn,1), . . . ,max
(n)(x1,1, . . . , xn,1)). Then by Proposition 3, Sort1(x1,1, . . . , xn,1) = Sort1(x1,1, . . . , xn,1) is also a function by an Sn-invariant deep neural network and Sort(x1,1, . . . , xn,1) is the function from I to ∆. When D > 1, we first consider Sort1(x1,1, . . . , xn,1). Since Sort1(x1,1, . . . , xn,1) gives a permutation on (x1,1, . . . , xn,1), for each (x1,1, . . . , xn,1), we can find σ ∈ Sn such that Sort1(x1,1, . . . , xn,1) = (Sort1(x1,1, . . . , xn,1)1, ...,Sort1(x1,1, . . . , xn,1)n) = (xσ(1),1, . . . , xσ(n),1).
Then we define
Sort(x) =  Sort1(x1,1, . . . , xn,1)1 · · · xσ(1),d · · · xσ(1),D ... . . . ... Sort1(x1,1, . . . , xn,1)i xσ(i),d xσ(i),D
... . . . ... Sort1(x1,1, . . . , xn,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 Sn-invariant. Take arbitrary τ ∈ Sn and fix x and σ ∈ Sn as above. Put τ · x = y. We show Sort(y) = Sort(x). Since Sort1 is an Sn-invariant function, we see Sort1(y1,1, . . . , yn,1) = Sort1(τ(x1,1, . . . , xn,1)) = (xσ(1),1, . . . , xσ(n),1) = (yσ(τ−1(1)),1, . . . , yσ(τ−1(n)),1). Then we have
Sort(y) =  Sort1(y1,1, . . . , yn,1)1 · · · yσ(τ−1(1)),d · · · yσ(τ−1(1)),D ... . . . ... Sort1(y1,1, . . . , yn,1)i yσ(τ−1(i)),d yσ(τ−1(i)),D
... . . . ... Sort1(y1,1, . . . , yn,1)n · · · yσ(τ−1(n)),d · · · yσ(τ−1(n)),D

=  Sort1(x1,1, . . . , xn,1)1 · · · xσ(1),d · · · xσ(1),D ... . . . ... Sort1(x1,1, . . . , xn,1)i xσ(i),d xσ(i),D
... . . . ... Sort1(x1,1, . . . , xn,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 Λ ◦ Φ = idF∆ and Φ ◦ Λ = idFSn . Since we have
Λ ◦ Φ(f) = Λ ◦ f ◦ Sort = (f ◦ Sort) ∆ = f, Λ ◦ Φ is equal to idF∆ . Similarly,
Φ ◦ Λ(f) = Φ ◦ f ∆ = f ∆ ◦ Sort = f, where the last equality follows from the Sn-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, ifA isO(ε−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 π : Rn×D → Rn−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 = (as,r) ∈ RnD 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 as,r = a′s,r holds for (s, r) 6= (σ−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 as,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
N (ε,∆, ‖ · ‖∞) ≤ |C(I)| − Eε−n(D−1)
n! + E′ε−n(D−1).
Since |C(I)| = ε−nD, we have the desired result.

heading: 4.2 PROOF FOR THE COMPLEXITY-CONTROL BOUND (THEOREM 2)
text: We utilize the results of ∆ and prove Theorem 2. The proof mainly contains the following two-step: i) show that the covering number of FSnDNN is equal to that of F∆DNN , and ii) bound the covering number of F∆DNN . The first step is provided by the following proposition. Proposition 4. For any ε > 0, we obtain
logN (ε,FSnDNN , ‖ · ‖L∞(I)) = logN (ε,F ∆ DNN , ‖ · ‖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 FSnDNN by the size of F∆DNN .
Proof of Proposition 4. For any f, f ′ ∈ FSnDNN , 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 logN (ε,FSnDNN , ‖ · ‖L∞(I)) by logN (ε,F∆, ‖ · ‖L∞(∆)). Suppose logN (ε,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 ∈ FSnDNN , there exists fj := f ∆j ◦ g ∈ F Sn DNN with corresponding j and it satisfies ‖f − fj‖L∞(I) ≤ ‖f ∆ − f ∆j‖L∞(∆) ≤ ε. Then, we obtain the statement.
The second step of this section is shown by the following proposition: Proposition 5. With an existing constant c > 0 and C in Lemma 1, for any δ > 0, we obtain
logN (2C∆δ,F∆DNN , ‖ · ‖L∞(I)) ≤ C
n! δp + log
( 2cB
δ
) .
Importantly, the result shows that the main term of the covering number is improved by n!, and it is a key factor to improve the overall generalization error.
Proof of Poposition 5. We bound a covering number of a set of C∆-Lipschitz continuous functions on ∆. Let {x1, ..., xK} ⊂ ∆ by a set of centers of δ-covering set for ∆. By Lemma 1, we set K = C/(n! δp) with δ with a parameter δ > 0, where C > 0 is a constant.
We will define a set of vectors to bound the covering number. We define a discretization operator A : F∆ → RK as
Af = (f(x1)/δ, ..., f(xK)/δ) >.
Let Bδ(x) be a ball with radius δ in terms of the ‖ · ‖∞-norm. For two functions f, f ′ ∈ F∆ such as Af = Af ′, we obtain
‖f − f ′‖L∞(I) = max k=1,...,K
sup x∈Bδ(xk)
|f(x)− f ′(x)|
≤ max k=1,...,K sup x∈Bδ(xk) |f(x)− f(xk)|+ |f ′(xk)− f(xk)| ≤ 2C∆δ,
where the second inequality follows f(xk) = f ′(xk) for all k = 1, ...,K and the last inequality follows the C∆-Lipschitz continuity of f and f ′. By the relation, we can claim that F∆ is covered by 2C∆δ balls whose center is characterized by a vector b ∈ RK such as b = Af for f ∈ F∆. Namely, N (2C∆δ,F∆, ‖ · ‖L∞(I)) is bounded by a number of possible b. Then, we construct an explicit set of b to cover F∆. Without loss of generality, assume that x1, ..., xK are ordered satisfies such as ‖xk − xk+1‖∞ ≤ 2δ for k = 1, ...,K − 1. By the definition, f ∈ F∆ satisfies ‖f‖L∞(∆) ≤ B. b1 = f(x1) can take values in [−B/δ,B/δ]. For b2 = f(x2), since ‖x1 − x2‖∞ ≤ 2δ and hence |f(x1) − f(x2)| ≤ 2C∆δ, a possible value for b2 is included in [(b1 − 2δ)/δ, (b1 + 2δ)/δ]. Hence, b2 can take a value from an interval with length 4 given b1. Recursively, given bk for k = 1, ...,K− 1, bk+1 can take a value in an interval with length 4.
Then, we consider a combination of the possible b. Simply, we obtain the number of vectors is (2cB/δ) · (4c)K−1 with a universal constant c ≥ 1. Then, we obtain that
logN (2C∆δ,F∆, ‖ · ‖L∞) ≤ (K − 1) log 4c+ log (2cB/δ) .
Then, we specify K which describe a size of ∆ through the set of covering centers.
Proof of Theorem 2 and 3. For Theorem 3, we combine the result in Proposition 4 and 5. For Theorem 2, we substitute the result in Theorem 3 into the well-known result (2), then obtain the statement.

heading: 4.3 PROOF FOR APPROXIMATION-CONTROL BOUND (THEOREM 4)
text: Proof of the approximation power also depends on the correspondence mapping Λ in Proposition 2. Although Proposition 2 claims that the correspondence holds for a function by deep neural networks, the similar discussion in the proof shows that it holds for a general invariant function.
Proof of Theorem 4. Let f∗ be an invariant function on I . Then by Proposition 2, we have a function f on ∆ such that f∗ = f ◦ Sort holds. By Theorem 5 in Schmidt-Hieber (2017), for enough big N , there exists a constant c and a neural network g with at most O(log(N)) layers and at most O(N log(N)) nonzero weights such that ‖f − g‖L∞(I) ≤ cN−α/p. Then, we have
‖f∗ − g ◦ Sort‖L∞(I) = ‖f ◦ Sort− g ◦ Sort‖L∞(I) = ‖f − g‖L∞(∆) ≤ ‖f − g‖L∞(I) ≤ cN−α/p,
where g ◦Sort is a neural network with at mostO(log(N))+K1 layers and at mostO(N log(N))+ K2 nonzero weights, whereK1 andK2 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.

heading: 5 DISCUSSION AND COMPARISON
text: 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.

heading: 6 CONCLUSION
text: 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.

Review summaries:
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. 

This paper presents a derivation of a generalization bound for neural networks designed specifically to deal with permutation invariant data (such as point clouds). The heart of the contribution is that the bound includes a  1/n! (i.e. 1 / (n-factorial)) factor to the major term, where n is the number of permutable elements there are in a data example (think: number of points in a point cloud). This term goes some way towards making the bound tight.