Improved Generalization Bound of Permutation Invariant Deep Neural Networks
Authors: Akiyoshi Sannai
Masaaki Imaizumi
Venue:  (2020)
Keywords: Deep Neural Network
Invariance
Symmetry
Group
Generalization

Abstract: We theoretically prove that a permutation invariant property of deep neural networks largely improves its generalization performance. Learning problems with data that are invariant to permutations are frequently observed in various applications, for example, point cloud data and graph neural networks. 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 $\sqrt{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.

Under review as a conference paper at ICLR 2020
IMPROVED GENERALIZATION BOUND OF PERMUTATION INVARIANT DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We theoretically prove that learning with permutation invariant deep neural net- works largely improves their generalization performance. Learning problems with data that are invariant to permutations are frequently observed in various applica- tions, for example, point cloud data and graph data. Numerous methodologies have been developed and they achieve great performances, however, understand- ing a mechanism of the performance is still a developing problem. In this paper, we derive theoretical generalization bound for invariant deep neural networks with ReLU activation to clarify their mechanism. Consequently, our bound shows that the main term of their generalization gap is improved by vnr. where n is a number of permuting coordinates of data. Moreover, we prove that an ap- proximation power of invariant deep neural networks can achieve an optimal rate, though the networks are restricted to be invariant. To achieve the results, we de- velop several new proof techniques such as correspondence with a fundamental domain and a scale-sensitive metric entropy.
INTRODUCTION
A learning task with permutation invariant data frequently appears in various situations in data anal- ysis. typical example is learning on sets such as point cloud, namely, the data are given set of points and permuting the points in the data does not change 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., 201 8a; Su et al., 2018; Li et al., 201 8b; 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 aceu- racy from theoretical aspects. Since invariant data are high-dimensional in general, learning theory claims that the sigeddimensionality 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 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 supervised-learning problem with m pairs of observations (X,, Yi) where X; are regarded as p- dimensional vectors, and X; can divided to n coordinates and each of them have = p/n dimen- sion. Also, let f denote function by a deep neural network which satisfies an invariant property, f(x) = f(a x)) holds for any & E R D where a is an arbitrary permutation of D-dimensional coordinates in æ. Also, we define Rm. (J) m =i=1 L(Y,, ((X.)) and R(S) = E[L(Y, as an empirical and expected loss value L(Y,, f(X).
m
Then, we show that following:
Theorem (Informal version of Theorem 2). Let Letf... f be a function by a deep neural network which takes p-dimensional inputs and invariant any permutations of coordinates. Then, for sufficiently

---

Under review as a conference paper at ICLR 2020
small E >> 0, we obtain
C
R(PS0)) I Rm (fS)
+ +O(oo((1/E),
n! mE
with probability at least O(e). Here, C is a constant independent of m and n.
As a consequence of Theorem the generalization bound is improved by vn! by the invariant property. Since the number of coordinates n is huge in practice, e.g. there are 2 1, 000 points in the point cloud data in Zaheer et al. (2017) and hence Vn! 2 102.000 holds, we show that the derived generalization bound largely improved by invariance. Further, we also derive a rate of approximation of neural networks with invariance (Theorem 4) and its optimality, thus show that an invariance property for deep neural networks does not reduce an expressive power.
From 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, correspondence between a function by invariant deep neural networks and a function on the funda- mental domain (Proposition 2). Thirdly, a volume of invariant functions with neural networks (Proposition 5). Based on the techniques, we can connect generalization analysis to the invariance of deep neural networks.
show one-to-one
develop a scale-sensifive covering number to control
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 show that the bound is improved by vnl.
We derive rate of approximation of invariant deep neural networks. The result shows that the approximation rate is optimal.
We develop several proof techniques achieve the bound such complexity analysis for a fundamental domain and a seale-sensitive metric entropy.
1.1 NOTATION
For vector b RR,, its d-th element is denoted by by. Also, b_d (bi...., bu- ba+1, bp) PD-1 a vector without by- llbll == (Ep=ab)) 4 is the g-norm for q E [0, oo]. For a tensor A E D2 (di, d2)-th element of A is written as Ad, For a function f Ω + R with set Q |l == (Jo (=)) denotes the - for q E oo). For subset A Ω2 fi, denotes the restriction of f to A. For integer 2, 2! Iī== denotes factorial of For a set Ω with a norm || Il. (E, 2, ||
II) == inf( Hwr و s.t. U {w || - wyll I }} 5 Ω} is covering number of Ω with >> O. For set S2 idg or id denotes the identity map on Ω namely ido(x)= = x for any x E Ω. For a subset C R", int( denotes the set of the inner points of A.
PROBLEM SETTING
2.1 INVARIANT DEEP NEURAL NETWORK
We define set of permutation S, in this paper. Consider E RaxD where n be a number of coordinates in x and D be a dimension of each coordinate. Then, an action o S, on x is defined as
(o z)i,d Io (1).dd i= l,.... n, d= I...,,, D,
here, is a permutation of indexes i. Also, define invariant property for general functions. Definition (S,, Sys-Ivaarian//Quiviiian Function). For a X C R we say that map f: X R is
Sn invariant (or simply invariant) if f(a x) = f(x) for any a E Sn and any x E X,
Sn equivariian (or simply equivariant) if there an S, action on RM and f(o x) =
a [xx) for any Sn and any X.
2

---

Under review as a conference paper at ICLR 2020
In this paper, mainly treat fully connected deep neural networks with ReLU activation function. The ReLU activation function is defined by ReLU(x)) = max (0, æ). Deep neural networks are built by stacking blocks which consist of a linear map and ReLU activation. More formally, it is ReL + b;), where W; E Rd.-idd, and b, E TR for ,.... H. Here, H is depth of the deep neural network and de width of the i-th layer. An output of deep neural networks is formulated as
function 74 Rd, + Rd++ defined by (x)
f(z) == ZH -H-1... Z2 Z1(x).
(1)
Let FANN be a set of functions by deep neural networks.
We also consider an invariant deep neural network defined follows:
Definition 2 (Invariant Deep Neural Network). f E FDNN is function by a S, -nninvariant deep neural network, f is a S,-invariant function. Let FDNN C FDNN be set of functions by S,,-ivarrian deep neural networks.
The definition is a general notion and it contains several explicit invariant deep neural networks. We provide several representative examples follow.
Example (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 (,,-., lj, an invariant linear layer h, and fully-connected layer f'. For each b,i = 1,.., its parameter matrix is defined
W = XI XI A 1]T,
which makes & as a layer-wise equivariant function. They show that f = f' ho o is an invariant function. Its illustration is provided in Figure 1.
Example 2 (Invariant Feature Extraction). Let e a mapping for invariant feature extraction which will be explicitly constructed by deep neural networks in Proposition 2. Then, function f f g where a function by deep neural networks with a restricted domain. Figure provides image.
2.2 LEARNING PROBLEM WITH INVARIANT NETWORK
Problem formulation: Let [0, 1]xx be input space with dimension p dD. Let be an output space. Also, let L, y x ) - IR. be loss function which satisfies sup,,y''> [y, 3/)) < and 1-Lipschitz continuous. Let P* (xx, y) be the true unknown distribution on Ix xx), , and for f I I V. R(f) (x (I()_l((_("X_X. Y']
the expected risk of f. Also, suppose we observe a training
dataset Dm : [(X,, Yi)..., (X,,, m. Ym)) of size m. Let (f' == m m- Em T()((x)) Y,) be the empirical risk of A goal of this study to investigate the expected loss R(f) with function from a set functions as hypothesis set.
Learning with Invariant Network: We consider learning with hypothesis set by invariant deep networks. Namely, fix an architecture of deep neural networks preserves fSnn E FS invariant function. Then, we evaluate the expected loss R()S.).
FDNN be an
Ej
l
f())
f(x)
Figure
The invariant deep neural network by DeepSets (Zaheer al. (2017)). & is equivariant layer, a linear invariant layer, and f' is function by networks.
The invariant deep neural network by a fully con- nected layer g and feature ex- traction layer e.
Figure 2:

---

Under review as a conference paper at ICLR 2020
3 MAIN RESULT
3.1 COMPLEXITY-CONEE BOUND
We show that the learning procedure with invariance largely improve the generalization perfor- mance of deep neural network by proving the improved bound for the generalization error of with invariance. We firstly derive Complexity distribution. The bound depends on a Complexity control of FDNN and the Rademacher complex- ity.
bound which holds with an arbitrary true
Theorem (Main Result 1). Let F FINN be a set of functions by Sn-invariant deep neural networks which are C& Liischitz continuous and bounded by B > 0. Then, for any fSa E FDNN and for any O, the following inequality holds with probability least 2C
201 n!. meP
2log(2og B/E) log (1/2s)
R(f5") S (f
+
m
where 01 > 0 are constants which are independent of and m.
Significantly, the main term J in Theorem 2 is improved by vn! in the denominator. Note that we regard as the main term since 12 is a logarithmic order in e. As huge in practice, e.g. number of points in point cloud data, the term n! largely improves the tightness of the bound.
We mention that e appears in the denominator of I and it looks a harmful term when p = nD large. However, the term is negligible with large because n! increases much faster than =DD
Namely, we can obtain n! = (nn") holds for any c > and E > 0 as n - cc.
Proof of Theorem utilizes a complexity control for FDN N As a preparation, we apply the well- known bound (e.g. slightly modified version of Theorem 10.1 in Anthony & Bartlett (2009)) and obtain
R(fSw) (f 2 log (e, DNN: ll |1 log(1/22
m
which describes generalization of fSn by the covering number log 2N (s, FNNNS || || Then, we bound the covering number by the following Theorem which plays key role to achieve the main result in Theorem Proof of Theorem depends on several newly developed results presented in
Section 4.
Theorem (Complexity Bound). Let feiF defined in section Then, with an existing constant
> 0, we obtain
log. N/ || (()=()) < nd. 52 + log 2cB
Remark 1 (Bound without invariance). The bound is general version of an ordinary learning I E FDNN which does not have invariance. Rigorously, suppose FDNN N is a set of functions which are Ca-Lipschitz continuous and bounded by B 0. Then, for any f E FDNN and ε 0, the inequality in Theorem 2 holds with n = 1.
Remark 2 (Bound for covering numbers). We mention that there another way to bound the covering number of FS. by a number of parameters (e.g. Theorem 14.5 in Anthony Bartlett (2009)). Such bound has fast order since its order is a logarithm of E. However, the bound has linear order in a number of parameters, hence it easily increases with large- scale- deep neural networks which possess huge number of nodes and edges. Moreover, such bound is independent of the volume the domain, hence we cannot obtain the scale-sensitive covering number. To avoid the problem, employ another strategy in Theorem 3.
3.2 APPROXIMATION-CONTIII BOUND
We investigate the approximation power of invariant deep neural networks to clarify how they can achieve small empirical loss. Although restrict the expressive power of deep neural networks
4

---

Under review as a conference paper at ICLR 2020
in the learning procedure, prove that 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 a > 0 be degree of smoothness. For f :::- + R. the Hölder norm is defined as
10 f((x) 08 f3)((²)
1a = max sup 10 f(x)] [ SET
max sup B= a. Taappaa
110 - x 11:0 1
Then, the Hölder space on / is defined
H = f cla [ffl < <oo..
Also, H3 = (f E Ho Il & B} denotes the B-radius closed ball in H
Intuitively, He is a set of bounded functions which are a-times differentiable. The notion of the Hölder space is often utilized in characterizing the optimal functions f (e.g. see Hhamidt-Hieber (2017)). We achieve the more detailed bound for the generalization enror with assuming f Hyg.
Theorem (Main Theorem 2). For any >> O, suppose FDNN has at most (log(L/=)))aee)) and O(e-P/a p/a log(1/e)) non-zero parameters. Then, for any invariant f H there is fsa E F such that
|1 (1 SE.
The result in Theorem 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 -pfa up 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.
PROOF AND ITS STRATEGY
4.1 FUNDAMENTAL DOMAIN AND IT'S CORRESPONDENCE
To handle the invariance property in our proof, we provide key notion to show the main result. Definition 4 (Fundamental Domain), Let G be a group acting on a set J. C J is said to be fundamental domain of J with respect to the action of G if A satisfy the following properties;
J = UsEG {a x x E A}.
int(A) 7 int( A) = @ for any F r E G.
In our case, we can take a fundamental domain explicitly.
Proposition Put [0, x Then
A {u E I I1,1 x2,1 2..2..2a. In,1]
fundamental domain of with respect the permutation action of Sn defined in Section 2.
Figure 3 provides A with and D 1. Intuitively, A is extracted feature space for invariant function. Any element of T corresponds to an element of A with an existing action in S., namely, we can obtain
I= Uoes, 1
Proof of Proposition 1. We confirm the first property of the fundamental domain, namely / Usea (o x E A). Take I. There is a0 E S, such that Ze(1).1 2 To(2), 2
Fo(n),1 Then by the definition of A, a- E A. Hence x {o E A). This

---

Under review as a conference paper at ICLR 2020
X3,1
x OOO
Sort(x) E
Sort
(g)
X
X21
Figure 4: The Sort layer (red) which converts g E FA
Figure 3: A fundamental do- main A (the green cone) in I (the blue cube) with n = 3 and D 1.
DNN to f = (g) E FDNN with n = D = 3. The Sort layer exchanges the first elements of each I; E RD.
implies the first property.
Ø1,1 > 12,1 > In.1] By the definition of our action, a int( A) frE 2o (a),1 > Ta 12))1 > ... > 2, [m).1) Hence
We confirm the second property. We have int(A) = Ex
a. int(A) n int(A) = for any a TEG.
We provide two important properties of A. Firstly, we start with showing that there is a one-to-one correspondence between deep neural networks on A and invariant deep neural networks /. To the aim, we consider set of functions on A by (not necessarily invariant) deep neural networks;
FANN {g A + R has the form (1)).
Then, obtain the following result:
Proposition There exists bijection map A S FNNN > FNNN- Further, for any f E FS FNNN A(F) is obtained by the restriction of J. namely N(J) - Sta, and for any g E FDNN. \- can be obtained by adding sorting layers appeared in the proof.
Figure 4 provides an image for A (g) for E FANN- For preparation for proof of Proposition 2, we define an explicit invariant deep neural network. For vector E IR for some N, let (21, =N) (resp. min (i) (z1...., 2n)) be a function which returns the j-th largest (resp. smallest) element { N We can easily see that these functions are a S, invariiatt func- tion. More strongly, we have the following proposition.
Proposition 3. (21, ,2), and min (5) (21,..., EN) are represented by an existing deep neural networks with an ReLU activation for any j = 1, I,...N. N.
Proof of Proposition 3. Firstly, since
max(21, 22) max(2; 21 22, 0) + 22, and min(21, 22) max(21 22, 0) +
hold, we see the case of = N = 2. By repeating max(zı, =2), we construct (2) NN) 2N). Namely, we prove the claim in the case of = and arbitrary N. At first, we assume N is even without loss of generality, then we divide the set {.1,...Ny) into sets of pairs [(11, ((=1,,)),.
and m
Then, by taking max operation for each of the pairs, we have {yi = max(211 22), ... UN/2 max(2N-1,
We repeat this process to terminate. Then we have (1x (2),.. 2N) it is represented by an existing deep neural network. Similarly, we have min (" EN). Finally, prove the claim for any N and & < j. max(() (21,..,, is represented by deep neural network. We construct nN) follows: since
2,... N by induction. Assume that
max (1 1) (2 = (max(i-1)) (ZI, EN) (if 24 S (2 (otherwise)
[ (2)) (2,....,zN)
holds, we have (i (2).) (2I...., 2N) = min min((maxé ()-x) ((max(i-)) (Z,) f= (....N)), By inductive hypoth- esis, the right hand side is represented by deep neural network.

---

Under review as a conference paper at ICLR 2020
Proof of Proposition 2. We first define sorting
layers which is S, invariant 1, put Sort (21,1....... (p.1) Then by Proposition 3,
network mapping from I to A. W.Wnen
(11,)). ... max(") (21,1, In,1))
Sort, (I1.11..... In.1) Sort (11,11.... In,1) also function by an S.n-invariant deep neu- In,1) is the function from / to A. When D > 1, we first consider Sort, (21,1...... In,1). Since Sort, (#1,1).... 2n,1) gives a permutation on ( for each (I1,2,.... [n,1), we can find E Sn such that
ral network and Sort(z1,
Sort, (I1,1..... In.1) (Sort, (1I. Fn.1),,.... Sort (#1,1).... .n..,,)))))))))))))))))))))))))) (Zo(1),1).... Fo(n).1).
Then we define
Sort (21,1)...,, Ini)l
Io(1),
Io(1),D
Sort(x)
Sort, (21,1,..., Ln,1)
Eo(i),d
Sort S In,1)n
La(n).d La(n).D
By the construction and the definition of A, Sort(æ) is the function to A. We confirm Sort(x) -x-invariant. Take arbitrary E S,, and fix and E Sn as above. Put show Sort(y) = Sort(z). Since Sort, is an Sn-invariant function, we see Sort, (3.,, 3n.1) = Sort, xn.1))
y. We
(Wo(r 1(0),,s-.. -o(r 1(0)).1). Then have Sort, (Vi. Vn,1)1 Va(r-1(1)),d
Sort(y) =
Sort, Sort, (11,11 1n.1)s
Ma(r (6).d
Ma(r (G)).
Sort, (111,1, ,,,,,,, 3n,1)n
yolr (()))d
yotr (x))
Sort (21,1...... 1n,1)1
To(1).d
To(1)DD
=
Sort, (21.1....,, In.1)s
(a(1),d
Da(1).D
Sort, ( 11 In11)n
Fo(n).d
To(n).
Sort(w))
where the second equality follows from 7 -- x. By using this function, we define the inverse of A. For any function f by deep neural network on A, we define ((f) = f Sort. We confirm A & idF, and O A id.... Since we have
A \ = Ao o Sort = (ʃ o Sort) = -z
o t is equal to idf,- Similarly,
to A(f) fIa fia o Sort =
where the last equality follows from the S,, -nvaiivareence of f. Hence, we have the desired result.
The second key property A is that we can measure its size. Since A included in I, we can naturally measure its volume by the Euclidean metric. By utilizing the property, evaluate its volume by a covering number of by the following lemma:
Lemma 1 (Covering bound for A). There is constant C such that for enough small we obtain
N(s, 160) <
n! gnD
Proof of Lemma 1. Let C(I) set of E-cubes which is a standard subdivision of We can easily that C(T) attains the minimum value s-nD of the number of e-cubes which is the covering of T.

---

Under review as a conference paper at ICLR 2020
We show that can find subset of C(T) whose cardinality is E n. + O(E-n(D-1), The strategy of the proof is as follows. At first, we calculate the number A of cubes in C(T) which intersect with the boundary of A. Then since the permutation the cubes which do not intersect with the boundary of - is free, if is O(E O(E-n(D-1)) D),, we can find the covering whose cardinality is =- m! +
O O(c-n(D-1)). Since a A is {ar E Fo- (1), 2 Fo (2)1 2 ... 2 Io-1((n,1)-- any boundary of A is of the form {2 I (1), ......------- (1), ((+1)) 2 2 2 (x))))
Fix a and i. Consider the projection ग : RTxD R which sends 26 1(),1 zero induces the map C(I) + C(=(T)), where C(T(T)) is of e-cubes which is the subdivision of (l) induced by C(T) Let ((T)aing denote the set of cubes in C(T) which intersect with the set Then we can see that is injective on C(T)aiag as follows. Let us denote a (Aa.r) E RnD the center of an g-cube in C()). Assume that there are two cubes in C(I)ding whose images by गे are equal. Let us denote the centers of two cubes by a and a' .Then we have (())= = 5 (aa) and hence asr d',r holds for (s, r) * (o (i), 1). Here, by our construction of s-cubes, cube (in C(T) intersect with B if and only if its center is on B Therefore, since two cubes are in C(I) diags we have a, (0),1 (i-1( and d' d/-1(1), d0-1((+1)11 Hence ag = holds for any rs, and two cubes equal and is injective C(T).
B = {x 7 (0)1 = Iig- -
Next, let (T) be the set of E-cubes in C(T) which intersect boundary of a A. We see that the cardinality of C'(1) is bounded by Ee-"(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 Pre(T) is injective, we see the number of cubes which intersect the component is bounded by the number of e-cubes in C(p(T)), hence --n(D-1), Put C(J)inn = C(I) CZ)).. Then each cubes in C(I) inn does not intersect the boundaries a A. Hence, there a a such that the number of cubes C(I) snn which are contained in a A is lower than [C())aml By adding the cubes which cover the boundaries of a A, we have the covering o A. Furthermore, by pulling back by a we have the covering of A. Hence, we have
(CTT) ED-n(D-1)
N(s, AI 1. (100)
E's-n(D-1),
Since |C(T) =- we have the desired result.
4.2 PROOF FOR THE COMPLEXITY-CONTRO BOUND (THEBREM
We utilize the results of A and prove Theorem 2. The proof mainly contains the following two-step: i) show that the covering number of DNN is equal to that of FDNN- and ii) bound the covering number of FA DNN- The first step is provided by the following proposition.
Proposition 4. For any > O, we obtain
NE, Il. (I.=())) = Nlo J F ll (1)=())).
The result shows that the functional by deep neural networks on I with invariance is well de- scribed by a set of functions on A without invariance. The key point of this result is that we can describe the effect of invariance restriction on F.S by the size of FA
Proof of Proposition 4. For any f. E we can obtain
FS DNN, there exists faa.fa E FA by Proposition 2. Then,
|l 1 = IlAia og - faa ogll==0) S llfia - Halllz
Based on the result, we can bound log Je, Suppose log We, (()) =; K is finite. Then, there exist flal. flak. and for {1,..., K) such as IlSia S(aille<(s) I Here, for any f E F there exists fy == fiaj o E F with corresponding j and it satisfies Il -fill<>(1) S IlSaa - -iaille>(s) $ Then, obtain the statement.
(()()) by (og,Nes, ()))
any fia Fa, there exists
8

---

Under review as a conference paper at ICLR 2020
The second step of this section is shown by the following proposition:
Proposition 5. With an existing constant > O and C' in Lemma 1, for any 8 > 0, we obtain
2eBB
log.N (1)=())) & n! de + log
Importantly, the result shows that the main term of the covering number is improved by m!, and it is a key factor to improve the overall generalization error
bound a covering number set of Ca-Lipschitz continuous functions on A. Let {Ii,,..,KK FK C A by set of centers of d-covering set for A. By Lemma 1, we set K = C/(nn 80) with å with a parameter 5 > 0, where C' is a constant.
Proof of Poposition
We will define set of vectors to bound the covering number. We define discretization operator A FA + g as
Aʃ /f. ((xx))
Let (x(x) be ball with radius 8 in terms of the || 1100 norm. For two functions f.f' E FA such as Af Af', we obtain
|lf (' k=I,..,K (
sup
[f(x) fxx)]
max k= (ax)
sup
[f(x) - f(xx)) + | (f(())) - f(xx)) S 2C
where the second inequality follows f(xx f' for all k 1,.,, K and the last inequality follows the C' C'-Liischitz continuity of and f'. By the relation, we can claim that Fa is covered by 2C 8 balls whose center is characterized by vector b E RK such b Af for f Fa. Namely, 62 FA. (1)) is bounded by number of possible b.
Then, we construct an explicit set of b to cover Fs. Without loss of generality, assume that T1...., IK IK are ordered satisfies such as ||T - Ik+illoo < 26 for k = 1...,, K 1. By the def- inition, f FA satisfies []]]l==(A) S B. bi f(x1) can take values in BB85, B/8). For b2 = fx2)), since |||] 02 I 28 and hence [x() - fx22) 2C a possible value for by is included in [(b, 26)/6, /8, (b1 26) Hence, by can take value from an interval with length given by. Recursively, given by for i..... K bb+1 can take value an interval with length 4.
Then, we consider a combination of the possible Simply, we obtain the number of vectors is (2cB/8) (4c) with universal constant 2 1. Then, we obtain that
1ogA(2Ca6,, FAill ||r>)) < (K - 1) log 4e + log (2cB/8).
Then, specify K which describe size of A 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 The- orem 2, we substitute the result Theorem 3 into well-known result (2), then obtain the state- ment.
4.3 PROOF FOR APPROXIMATION- BOUND (THEOREM 4)
Proof of the approximation power also depends on the correspondence mapping A in Proposition 2. Although Proposition claims that the correspondence holds for 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 Then by Proposition 2, we have function f on A such that f* = fo Sort holds. By Theorem 5 in Schmidt-Hieber (2017), for enough big N, there exists a constant e and a neural network with at most (log(N)) layers and at most ON log(N)) nonzero weights such that |lf -ll (n) S cN a/p, Then, we have
Ilf g Sort|I>>(n) Ilf Sort g Sort|I1.>(n) Il )llx)(a) $ Ilf olle>(()) S cN-aa/p

---

Under review as a conference paper at ICLR 2020
where g o Sort is neural network with at most ([log(N)) + K layers and most (N log)N) + K2 nonzero weights, where 11 and K₂ are the number of layers and the number of nonzero weights of the neural network expressing Sort respectively. By replacing N with have the desired inequality.
5 DISCUSSION AND COMPARISON
We discuss the technical non-triviality of our result. One can consider that our result seems straight- forward, because the improvement by vn! looks a kind 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 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 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 vT, where T is 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 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 gets much tight by the invariant property, rigorously, the bound is improved by vn! where n a number of permutation-invarinn 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 ReLU activation can achieve the optimal approximation rate for smooth functions. By the results, our theory shows a great advantage of deep neural networks.
coordinates.
As 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.
REFERENCES
Martin Anthony and Peter L Bartlett. Neural network learning: f cambridge university press, 2009.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalizedd margin bounds for 2017.
neural networks. In Advances in Neural Information Processing Systems, pp.
Felix A Faber, Alexander Lindmaa, O Anatole Von Lilienfeld, and Rickard Armiento. Machine learning energies of 2 million elpasolite (a b c 2 6) crystals. Physical review letters, 117(13): 135502, 2016.
Jiaxin Li. Ben M Chen, and Gim Hee Lee. So-net: Segf-organizing network for point cloud analysis. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9397- 9406, 2018a.
10

---

Under review as a conference paper at ICLR 2020
Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Con-
volution on x-transformed points. In Advances in Neural Information Processing Systems, pp- 820-830, 2018b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. arXiv preprini arXiv: (ee.//91.0999 .03342994222 2019.
Michelle Ntampaka, Hy Trac, Dougal J Sutherland, Sebastian Fromenteau, Barnabás Póczos, and Jeff Schneider. Dynamical mass measurements of contaminated galaxy clusters using machine learning. The Astrophysical Journal, 831(2):135, 2016.
Siamak Ravanbakhsh, Junier B Oliva, Sebastian Fromenteau, Layne Price, Shirley Ho, Jeff G Schneider, and Barnabás Póczos. Estimating cosmological parameters from the dark matter dis- tribution. In JCML, pp.
2016.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint 1rXXvv1903.0111 2019.
Johannes Scchidt--Heebee Nonparametric regression using deep neural networks with relu activation function. arXiv preprint arXiv: /w0./00000000 06633, 2017.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues. Generalization error of invariant classifiers. arXiv preprint arX14:1610.04574, 2016.
Hang Su, Varun Jampani, Deqing Sun, Subhransu Maji, Evangelos Kalogerakis, Ming-Hsuan Yang. and Jan Kautz. Splatnet: Sparse lattice networks for point cloud processing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2530-2539, 2018.
Yifan Xu, Tianqi Fan, Mingye Xu, Long Zeng, and Yu Qiao. Spiderenn: Deep learning on point sets with parameterized convolutional filters. In Proceedings of the European Conference Computer Vision (ECCV), pp. 87-102, 2018.
Yaoqing Yang, Chen Feng, Yiru Shen, and Dong Tian. Foldingnet: Point cloud auto-encoder via deep grid deformation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 206-215, 2018.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pp. 3391-3401, 2017.


Reviews:
[{"review_id": "rJx0u1p19B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides generalization bounds for permutation invariant neural networks where the learning problem is invariant to the permutation of input data. \n\nUnfortunately, the technical value of the content and its novelty is very limited since the proof reduces to a very basic argument that counts invariances (which is simply n! where n is the number of invariant dimensions) and uses a standard approach to give a generalization bound. Therefore, I don't think the results does not help us with better understanding of permutation invariant neural networks. \n\nUnfortunately, the paper has several typos and mistakes as well. Another non-technical issue is that apparently authors have removed the ICLR format and reduced margin to fit the paper in 10 pages which is against the spirit of page limit.\n\n***********************************\n\nAfter author rebuttals:\n\nAfter reading authors' response and reading the proofs, I realize that the formal proof is not trivial and requires more work that I assumed. However, I do not understand how this work can improve our understanding of permutation invariant networks. Therefore, I think the contributions are not significant enough for publication and my evaluation remains the same.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklWqgGrcr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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.\n\nThe 1/n! factor in the bound may be an interesting development  but the novelty does appear to be limited.  Also, the authors fail to discuss that --  as part of that same term -- there is a factor: (1 / (epsilon^p)), where p is the dimension of the input and epsilon is a small error term. As p is proportional to n, and epsilon is quite small, this term could well dominate the factorial in many practical settings. A discussion of the relation between these terms is appropriate and seems to be missing.\n\nClarity:\nIn general the paper is fairly well written, but there are multiple instances of missing articles and strange idiom violations (eg. p. 4, remark 1: \"such the bound\" versus \"such a bound\")\n\nMore seriously, the proof of Lemma 1 was quite hard to follow (esp. the second paragraph). I would suggest putting less emphasis on the relatively straightforward construction of the sorting mechanism in Propositions 2 and 3, and use the space to more clearly detail the proof of Lemma 1, which is, after all, the heart of the contribution.\n\nI also found the proof of proposition 4 too confusing to easily follow. What is the interpretation of the indices (1, ..., K) on the functions?\n\nFinally, I would have liked to see some interpretation of the findings in a discussion section (or in an extended conclusion).   \n\nMinor issues:\n\n- First sentence of the abstract is difficult to parse and does not seem like an accurate assessment of the contribution of the paper. \n\n- Paragraph 2 of the introduction presents a sequence of argument whose logic seems inconsistent to me. There is a drift from a discussion of generalization of neural networks to a mention of work on the very distinct topic of the representational capacity of neural networks (i.e. universal approximation property of neural networks). The linking text \"To tackle the quesiton, ...\" is not appropriate.\n\n- Unlike Example 1, Example 2 (p.3) is not helpful in motivating the permutation invariant neural networks. The definition makes direct reference to Proposition 2 that will not be introduced for another 3 pages. \n\n- In Sec. 4.1, it seems like a phi symbol is used when I believe a null symbol was intended\n\n- Proposition 3: \"max( z_1, z_1 )\"  should be \"max( z_1, z_2 )\" with the adjustment carrying through to the other side of the equals.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkeJKjc0Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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. \n\nPros:\n1. The paper appears to be mathematically rigorous, and at the same time, is straightforward to follow, with useful intuitions provided whenever required. \n2. 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.\n\nCons:\n1. 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.\n\n[a] Generalization Error of Invariant Classifiers, Sokolic et al., ICML 2017.\n\n2. The paper has several typos and grammatical errors through out, which are easily fixable though!\n\nOverall, 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. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proves a generalization bound for permutation invariant neural networks (with ReLU activations). While it appears the proof is technically sound and the exact result is novel, reviewers did not feel that the proof significantly improves our understanding of model generalization relative to prior work. Because of this, the work is too incremental in its current form.
Decision: Reject