A PAC-Bayesian Generalization Bound for Equivariant Networks
Authors: Arash Behboodi
Gabriele Cesa
Taco Cohen
Venue: NeurIPS 2022 Accept (2022)
Keywords: generalization error
equivariant networks
group representation
PAC Bayesian

Abstract: Equivariant networks capture the inductive bias about the symmetry of the learning task by building those symmetries into the model. In this paper, we study how equivariance relates to generalization error utilizing PAC Bayesian analysis for equivariant networks, where the transformation laws of feature spaces are deter- mined by group representations. By using perturbation analysis of equivariant networks in Fourier domain for each layer, we derive norm-based PAC-Bayesian generalization bounds. The bound characterizes the impact of group size, and multiplicity and degree of irreducible representations on the generalization error and thereby provide a guideline for selecting them. In general, the bound indicates that using larger group size in the model improves the generalization error substantiated by extensive numerical experiments.


A PAC-Bayesian Generalization Bound for Equivariant Networks
Arash Behboodi" Qualcomm Al Research, Amsterdam behboodi@qta qualcomm. com
Gabriele Cesa"
Qualcomm Al Research, Amsterdam
AMLab, University of Amsterdam gcesauqti. coapeetqtiiquaalco....mm qualcomm..m..m...
Taco Cohen
Qualcomm AI Research, Amsterdam tacos@qti.. qual
gumm.com.... comm. com
Abstract
Equivariant networks capture the inductive bias about the symmetry of the learning task by building those symmetries into the model. In this paper, study how equivariance relates to generalization еггor utilizing PAC Bayesian analysis for equivariant networks, where the transformation laws of feature spaces are deter- mined by group representations. By using perturbation analysis of equivariant networks in Fourier domain for each layer, we derive norm- based PAC-Bayesian generalization bounds. The bound characterizes the impact of group size, and mul- tiplicity and degree of irreducible representations on the generalization error and thereby provide guideline for selecting them. In general, the bound indicates that using larger group size the model improves the generalization error substantiated by extensive numerical experiments.
Introduction
Equivariant networks are widely believed to enjoy better generalization properties than their fully- connected counterparts by including inductive bias about the invariance of the task. A canonical example is convolutional layer for which the translation of the input image (over R²2 leads to translation of convolutional features. This construction can be generalized to actions of other groups including rotation and permutation. Intuitively, the inductive bias about invariance and eguivariance helps to focus on features that matter for the task, and thereby help the generalization. Recently, many works provide theoretical support for this claim mainly for general equivariant and invariant models. In this work, however, we focus on a class of equivariant neural networks built using representation theoretic tools. As in Shawe-Tayyllla Taylor and Wood [1996), [Cohen and Welling (216b)) WWiler et al.) [0188]], this approach can build general equivariant networks using irreducible representations of group. An open question is about how to design feature spaces and combine representations. Besides, the question of impact of these choices on generalization remain. well understood how to build G' equivariant model when G' is finite, the choice of the group G to consider is not always obvious. Indeed, using a subgroup H < G smaller than G is usually sufficient to achieve significant improvements over non-equivariant baseline. Moreover, the symmetries G of the data are often continuous, which means G-equivariance can not be built into the model using group convolution design in Cohen and Welling (016aa In such cases, the most successful
the other hand, while is rather
"equal contribution "Qualcomm Al Research is an initiative of Qualcomm Technologies, Inc.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

approaches approximate it with a discrete subgroup H < G, e.g. see Weiler and Cesa 2019 for the G = ((2) case. In addition, the choice of the equivariance group H can affect either the complexity or the expressiveness of the model and, therefore, its generalization capability, depending on how the architecture is adapted. For instance, if one can not freely increase the model size, using larger group H only increases the parameters sharing but reduces the expressiveness of the model. For this reason, using the whole group might not be beneficial even when feasible. In that line, we consider how the choice of group size affects generalization.
Contributions In this paper, we utilize PAC Bayes framework to derive generalization bounds on equivariant networks. Our focus is on equivariant networks built following Weiler al. [201 8a]. Cohen and Welling [2166b]. We combine the representation theoretic framework of Weiler and
Cesa [2019] with PAC-Bayes framework of Neyshabur et al. (2088) to get generalization bounds on equivariant networks as a function of irreducible representations (irreps) and their multiplicities.
Different from previous PAC-Bayes analysis, we derive the perturbation analysis in Fourier domain. Without this approach, as we will show, the naive application of Neyshabur et al. 2018 lead to degenerate bounds. As part of the proof, we derive tail bound on the spectral norm of random matrices characterized as direct sum of irreps. Note that for building equivariant networks, we need to work with real representations and not complex ones, which are conventionally studied in representation theory. The obtained generalization bound provide new insights about the effect of design choices on the generalization error verified via numerical results. To the best of our knowledge. this is the first generalization bound for equivariant networks with an explicit equivariant structure. We conduct extensive experiments to verify our theoretical insights, as well as some of the previous observations about neural networks.
2 Related Works
Equivariant networks. In machine learning, there has been many works on incorporating symme-
tries and invariances in neural network design. This class of models has been extensively studied
from different perspectives Shawe- Taylor 1993] 1989]. Kondor and Trivedi (2018). Cohen et al.
[2018] Mallat 20122] Dieleman et al. [2016), Cohen and Welling 62016a b). Worrall et al. [2017].
Weiler et all 22118bba a Thomas et al. [2018] Bekkers et al. [2018]. Weiler and Cesal [2019]. Bekkers
2020). Defferrard et al. [2019]. Finzi et al. 2020). Weiler et al. [2021], Cesa et al. [2022] to mention
only some. Indeed, the most recent developments in the field of equivariant networks suggest
design which enforces equivariance not only at a global level Laptev et al. [016)] but also at each
layer of the model. An interesting question is how particular choice for designing equivariant networks affect its performance and in particular generalization. A related question including this inductive bias helps the generalization. The authors in [Sokolić et al. [2017a] consider general invariant classifiers and obtain robustness based generalization bounds, as in SSokoli et al. 2017b), assuming that data transformation changes the inputs drastically. For finite groups, they reported a scaling of generalization eтror with 1/ [H]] where H is the cardinality of underlying group. In Elesedy| [002]). the gain of invariant or equivariant hypotheses was studied in PAC learning framework, where the gain in generalization is attributed shrinking the hypothesis space to the space of orbit representatives. A similar argument can be found in Sannai et al. (202T) where is shown that the invariant and equivariant models effectively operate on shrunk space called Quotient Feature Space (QFS), and the generalization error is proportional to its volume. They generalize the result of Sokolić al. [017a]] and relax the robustness assumption, although their bound shows suboptimal exponent for the sample size. Similar to Sokoliē et al. 2a], they focus on scaling improvement of the generalization error with invariance and do not consider computable architecture dependent bounds. The authors in Lyle et al. [2200] use PAC-Bayesian framework to study the effect of invariance on generalization, although do not obtain any explicit bound. Bietti and Mairal 2019 studies the stability of models equivariant to compact groups from RKHS point of view, relating this stability Rademacher complexity of the model and a generalization bound. The authors in Elesedy and Zaidi [202T) provided the generalization gain of equivariant models more concretely and reported VC-dimension analysis. Subsequent works also considered the connection of invariance and generalization Zhu et al. (202T) In contrast with these models, we consider the equívariant networks with representation theoretic construction. Beyond generalization, we are interested getting design insights from the bound.
whether
2

---

Generalization error for neural networks. A more general study of generalization error in neural networks, however, has been ongoing for some time with huge body of works on the topic. We refer to some highlights here. A challenge for this problem was brought up in Zhang et al. (2017), where it was shown using the image-net dataset with random labels, that the generalization error can be arbitrarily large for neural networks, as they achieve small training error but naturally cannot generalize because of random labels of images. Therefore, any complexity measure for neural networks should be consistent with the above observation. As result, uniform complexity measures like VC-dimension do not satisfy this requirement as they provide a uniform measure over the whole hypothesis space.
In this light, recent works related the generalization errors quantities like margin and different norms of weights for example in, among others, Wei and Ma [209)] Sokolić et al. (2077), Neyshabur
al.
2018], Arora et al. 2018), Bartlett et al. [2017]. Golowich al. [2018], Dziugaite and Roy
[201 8a Long and Sedghi [2019], Vardi et al. [2022]. Ledent et al. 202T]. Valle-Pérez and Louis
2020 Some of these bounds are still vacuous or dimension-dependent (see liang et al. [2020] for
detailed experimental investigation and Nagarajan and Kolter (201)). Koehler et al. [222]] Negrea
ct al.
202T] for follow-up discussions on uniform complexity measures). Class of convolutional
neural networks are particularly relevant they can be considered as special case of equivariant
models. These models are discussed in Pitas et al. (2019). Long and Sedghi 2019), Vardi et al. [2022],
Ledent et al. [2021]. We choose PAC Bayesian framework for deriving generalization bounds. There are many works on PAC Bayesian bounds for neural networks Neyshabur et al. (2018), Biggs and Guedj] [022). Dziugaite and Roy [2017 2018b al. Dziugaite al. 2020 ranging from randomized
and deterministic bounds to choosing priors for non-vacuous bounds. Our method combines the
machinery of Neyshabur et al. 2018 with representation theoretic tools.
3 Background
3.1 Preliminaries and notation
We fix some notations first. We consider a classification task with input space X' and output space V. The input is assumed to be bounded in fz-norm by B. The data distribution, over X' x y, is denoted by D. The hypothesis space, H. consists of all functions realized by L-layer general neural network with 1-Lipschitz homogeneous activation function:] The network function, fw(() with fixed architecture, is specified by its parameters W (W1, (W....., Wt). The operations on W extended from the underlying vector spaces of weights. For any function f(),, the k' o'th component of the function is denoted by f(x) [k] throughout the text. For loss function H X ) + R. the empirical loss is defined by L(f) == 1
m Σ L(f, (I,, 34)) and the true loss is defined by L(f) B( [L,,, (x. y)}]. For classification, the margin loss is given by
(fw)) = (a.g))> fw (xx())lv) S 7 + max fw (w(()))))
374
The true loss of a given classifier is then given by [(fw) Lo (sw) The empirical margin loss similarly defined and denoted by É. In this work, we consider invariance with respect to transformations modeled as the action of a compact group G. See Supplementary 7 for a brief
introduction to group theory and the concepts that we will use throughout this paper.
3.2 Equivariant Neural networks
We provide a concise introduction to equivariant networks here with more details given in Supple- mentary We adopt a representation theoretic framework for building equivariant models.
Example. Consider a square integrable complex valued function f with bandwidth defined on
2D-rotation group (2( and represented using its Fourier series as ʃ(0) = >BB O2 eig Consider an equivariant linear functional of /f mapping
another function on S2).). In Fourier space, the linear transformation is given by Wa with a as the Fourier coefficient vector a = (ao..... ..... ag). The action of rotation group on the input and output space is simply given by f() + f(O 0o) with O as the rotation angle, or equivalently in Fourier space as a linear transformation a + p(Oo)a
The function a(-) is homogemeous if and only if for all æ and E E. we have (Ax)) (z)
3

---

Layer /
Layer
Vo
Vo
W, (+b))
4P1
4/
01.1
:
Vg
BBB
Wi(vs)
68.1
0g.1
Figure An equivariant layer maps the coefficients corresponding to each frequency (irrep) vb to new set of coefficients based on the matrix (i)),, which include blocks of ( i,5) with i [m] and j [mr,0l-
with p(0)) = diag (1, e. e. e.....--.. BBB... Since it holds for all a, Equivariance condition means W WP(O)) p(0,) W for all Go. which implies that W should be diagonal. A general feature space can be built by stacking multiple linear transformations W. and more flexibly, by letting the transformations acting only on some of the frequencies (for example, transformation that only on a for frequency B). This machinery can be generalized to represent equivariant networks with respect any compact group, by using irreducible representations (irreps) of the group in place of complex exponential einll of this example. The key is to notice that ein0's are irreps of SO(2).
General Model. Consider Multi-Layer Perceptron (MLP) with L layers with the layer I [L] given by the matrix Wi E R xq-x, The action of the group H on layer determined by linear transformation Pt, which is called the group representation group element h E linearly transforms the layer by the matrix pi (h). The matrix Wi is equivariant w.r.t. the representations o and Pt-1 acting its input and output if and only if for all E H, we have:
8 (see section 8 for more details).
W Wipt-1 Pr))
Representation theory provides a way of characterizing equivariant layers using Maschke's theorem and Schur's lemma. The key step is to start from characterizing the irreducible representations (irreps) {w} of the group H. As we will see, irreps are closely related to generalization Fourier analysis for functions defined on H. Maschke's 's theorem implies that the representation decomposes into
QT', where mı, is the number of times the irrep yb present in the representation pt, that is, multiplicity. Each v is dim@ X dimg matrix, and the direct sum is effectively a block diagonal matrix with matrix irreps &i on the diagonal. Through this decomposition, we can parameterize equivariant networks in terms of irreps, that is in Fourier space. Defining Wi = Q, WiQi-1, the equivariance condition writes as
direct sum of irreps as = Q ① +
Di +b
1,,
Wi
W
The block diagonal structure of +
induces similar structure on Wi (see Figure 6). By Wi j,,,, denote the block in W that relates i'th instance of th to j'th instance of v/2, with E [m--109] and [m) as:
mi, t=l
+
vh, (.
(1) (112,, v).
Schur's lemma helps us to characterize the equivariant kernels. Note for neural network implemen- tation, we need to work with version of Schur's lemma for real-valued representations given in Supplementary X Schur's lemma implies that vh o 4/2, the block needs to zero guarantee equivariance. Otherwise, needs to have one of the three forms in Supplementary g depending

---

the rype of 11 To simplify the notation, we write (7,,,,,,1) as Wi(b,j.i). As it is shown in Supplementary the matrix Wi) can be written the linear sum
W1(, = m1) Biwii
where (w),i k= are learnable parameters with fixed matrices BL The value of co either 1,2 or The structure of Bl. changes according each type Cp. Each layer is parameterized by the matrices Wi()), which include cs parameters (1)) E R with E (m-1,4] and j (m Therefore, for each layer, there will be Eg m parameters with the width the layer given as Σe mi,y dimg. Note that, if x = Wi then
c = -1 where x; = Q, xt The non-linearities should satisfy equivariance condition have full end-to-ent equivariance. An important question is which representation it of И should be used for each layer. For the imput, the representation is fixed by the input space and its structure. However, the intermediate layers choose pi by selecting irreps and their multiplicity. We explain how this choice impacts generalization bounds. We consider a general equivariant network denoted by fw with the parameters of I'th layer given by W (+) for all irreps v E [m--1.) and E [m,
4 PAC-Bayesian bound
We derive PAC-Bayes bounds for equivariant networks fw presented in the previous section. Although the proof follows a similar strategy in Neyshabur et al. [2018]. it differs in two important aspects. First, the weights of equivariant MLPs have specific structure requiring reworking proof steps. Second, we carry out the analysis in Fourier domain. In Supplementary I we also show that naively applying norm-bounde of Neyshabur et al. 2018) cannot explain the generalization behaviour of equivariant networks. A simple version of our result is given below.
Theorem 4.1 (Homogeneous Bounds for Equivariant Networks). For any equivariant network, with high probability have:
Ihe Wile 72mm
E vis
Wi(b,i,))
dimo
C(fw) - (f,)
Σ VM(I.n)
Σ
|ill
where 1) E (0, 1) and
Ei=1
Ei=EE mi
M(,n) = log
max
1-
The complete version of the theorem is given in Theorem 9.1
We comment briefly on the proof steps. PAC-Bayesian generalization bounds start with defining a prior P and posterior Q over the network parameters. The network is drawn randomly using Q which is also used evaluate the average loss and generalization error. The PAC-Bayesian bound provides a bound on the average generalization етгог of networks randomly drawn from Q (Section fe-randomize the bound and to obtain the generalization error for a specific instance fw H. Among different strategies, we follow the perturbation based method of Neyshabur et al. 2018 The main idea to carefully define a posterior Q, such that the networks randomly drawn from Q have small distance with the specific fw. and therefore the loss averaged over Q can be used to bound the loss fw. One way to choose Q to define a Gaussian distribution around the parameters W and choose the variance to control the output perturbation (Section 4.2
4.1. The next step
In what follows we provide more details about these steps.
4.1 PAC-Bayesian Bounds for Randomized Networks
The starting point is the PAC-Bayes theorem Langford and Shawe-taylor (002 McAllester (1988. which provides generalization bound on randomized classifiers. If the function chosen randomly
5

---

from a distribution Q, then define the average losses as ((Q) E(fef(f) and ((Q) By~af(f).
We use the following version from Germain et al. 20091
Lemma 4.2. For any hypothesis space H. let P be a probability distribution on H. Then for all 5 E (0, 1]. with probability 1 - 6. for all Q on H. we have:
D(QIIP) + log({(m)/0)
((Q) - (QQ)
(4)
2m
where E(m) == Em= (k/m(/))*(1 k/m)"
In PAC-Bayes vernacular, the distributions P and called prior and posterior distribution on H. This indicates that the distribution P and Q are chosen independently with Q typically chosen based the training data and the obtained model, and P chosen independently based any information available before training. Choosing an appropriate prior plays a central role in getting non-vacuous bounds. For instance in Dziugaite and Roy [017]. the prior P is chosen using a separate dataset not used during training. Lemma 4.2 provides immediately generalization bound for randomized equivariant classifiers. The hypothesis space parameterized by the network parameters W, which contains kernel parameters (tb). We choose a prior distribution P as zero-mean normal with covariance matrix a² I over the parameters. The posterior Q is chosen as normal distribution with the final parameters in, (+) mean value and the same covariance matrix I²1. The KL-divergence in the PAC-Bayesian theorem is then given by:
D(QII El.ha || |001 (1)
(5)
20
The generalization bound depends on the sum of the norm of kernels. In the next step, we de- randomize the bound to get bound on the generalization error of fw.
4.2
De-Randomization and Perturbation Bounds
Our de-randomization technique follows closely that of Neyshabur et al. 2018). We provide the sketch of derivations here, and the full proof is relegated to the supplementary materials. To de- randomize the previous bound, a common step is to choose Q such that the probability of margin violation is controlled. Let Sw be defined
Sw = (h H
fwlloo 5//4}.
(6)
Any function on this set can change the margin of fw at most by 7/2. Therefore, for any h. L(fw) S (h), which implies [(fw) S (Q) if Q supported only on this set. Similarly (Q) < L. (fw). To choose Q first, we characterize the output perturbation of equivariant networks for a given input perturbation. Next, we determine the variance a such that the output perturbation is bounded by 7/4 with probability] The first step is the perturbation analysis.
Lemma 4.3 (Perturbation Bound). For neural network fwr(-) with input space of fz-norm bounded by B, and for any weight perturbations U (UI,..., UL), we have:
[w - ffv(2) 12 S eB
II W
Σ
L
U.
For equivariant networks, where the weights are parameterized as in eq. perturbation U₁ is bounded as
the spectral norm of the
||Uil22 <
max V ISigmi-1
max
mi- L.V
(8)
dim
The first inequality is already given in Neyshabur al. 2018 The inequality g will be shown in supplementary materials.
"This value be changed to any probability with proper adjustments. See the supplementary materials.

---

The perturbation bound already suggests the benefit of equivariant Kernels. As it will be shown in Supplementary materials, the equivariant kernels w.r.t. satisty
W
12
[ dime
which the smallest possible norm (compare with general relation for dimy dim, matrices:
[ 2 / || [)). Therefore, the term aime (V....0 in the perturbation bound is Vdiug
already tight.
The perturbation bound helps defining a posterior Q by adding zero-mean Gaussian perturbations (t)) of variance o² to the learnable parameters (+))) The output perturbation is given by the above theorem terms of norm of U. The following lemma controls the norm of this random matrix, and thereby the output perturbation.
Lemma 4.4. Consider a random equivariant matrix Uj defined by i.i.d Gaussian (0, o²) choice of un,55 (W), eq. We have:
P [1ill2 2 a max
Σ mi ct
(10)
The proof is given in supplementary materials. With Lemma 4.4 we can choose the variance a² such that the output perturbation does not violate the intended margin. Using an union bound over all layers, one finds that by choosing t log (2 (2 Eg m..)). with probability least 1 the following inequality holds for every layer / [L]:
Uill < max m log >Σ my
(1I)
We can use this bound jointly with the perturbation bound eq. 7 to choose a such that the margin is below 7/4 with high probability. Note that the chosen in this way is a function of learned weights. This cannot be the case because of the prior P should trick for circumventing this issue is to select many priors that can adequately cover the space of possible weights, and take the union bound over it. The complete proof of the theorem is given in Supplementary where we also consider special cases of this generalization bound for group convolutional networks Cohen and Welling 2016a]
fixed prior to learning.
Remarks on the generalization error from the theory. The generalization error of Theorem contains multiple terms. First, term v is a hyperparameter, which will fixed to 1/2 for rest. The term ((I 1) encodes the multiplicity and type of used irreps and their impact the generalization error. Let the hidden layer dimension ct = En dim, mi, be fixed constant. For Abelian groups, all real irreps are at most 2-dimensional, therefore, restricting the network to 2-dimensional irreps, we have:
Σle Ci 2(1 7)
M(1, 1) = -log
max (5m4-1..
The bound can controlled further by appropriate choice of m my Cy. which favors smaller multiplicity and type ey. Therefore, the bound favors using different irreps instead of repeating them. For non-abelian cases, irreps can have larger dimg, which keeping the layer dimension Cj fixed,
amounts to smaller multiplicity. This can improve the sum El E mhy in M 17) and indicates potential improved generalization for non-abelian groups. For dihedral groups, which is in general non-abelian, the real irreps are also at most two dimensional, however, type Co. 1. Note that for finite groups, there is connection between irrep degrees and group order H = Σ dim /cg. The impact of group size manifests itself in the whole generalization error term. We numerically verify this in the experimental results. The inverse dependence margin 7 is expected and similar to other
7

---

Freq. F=1
Freq. F=2
Freq. F=3
Freq. F=4
Freq. F=5
Freq. F=6
1.25 166
1.00
0.75
0.50
Bound
0.25
0.06
0.05
12
0.00
16
0.03
18
24
0.02
Group
0.2
0.3
0.4
0.2
0.3
0.4
0.2
0.3
0.4
0.2
0.3
0.4
0.2
0.3
0.4
0.2
0.3
0.4
Generalization Error
Dy
(Ist row) and the one in Supplementary (2nd row) on the synthetic O(2) datasets with different frequencies. The bound from Supplemen- tary II clearly does not capture the effect of group equivariance.
Figure 2: Comparison between the bound in Theorem 4.1
works for instance Neyshabur et al. 2018). The rest of the terms contain different norms of neural network kernels. We discuss them more in connection with Neyshabur al. (2018]
Comparison to Neyshabur et al. (2018). There are two main differences with the bound in Neyshabur et al. [2018]. First, their bound has a norm dependence of Ô (CL I E | || while in our result, the Frobenius norm includes an ad-
ditional scaling of 1/ dimy in (..)) /ddmm.... This term is strictly smaller in our bound for dimg > 1. The second difference is the term ((,)(, which is replaced with 122 In( Lh) where the layer width. In our case, the layer width is a = En dim Mi,e- Choosing all layer widths equal to h, we recover the In(Lh) term from Neyshabur et al. 2018 in our bound.
The remaining term is O (E, mi = my and same dimension dim dim for all irreps, that is, N dim my with N being the number of used irreps. Then, we get term as O (h² /2/NN dim)²). As long as the multiplicity my is smaller than N dim, i.e. number of used irreps times their dimension, our bound is strictly tighter. Intuitively, this means that using more diverse irreps leads better generalization. See Section for more detailed discussions.
2) As an example, assume the same multiplicity
Experiments
In this section, we also validate the theoretical insights derived in the previous section. More experiments and discussions are included in Supplementary 12
We have used datasets based on natural images and synthetic data. In all experiments, we consider data symmetries G which are subgroups of the group O(2) of planar rotations and reflections. This includes a number of finite/continuous and conmuuaaiveenon-commuuase
groups, particular Cv (N rotations), Dy (N rotations and reflections), SO(2) (continuous planar rotations) and ((2) itself (see Supplementary (7). Moreover, all models are based on group convolution over a finite subgroup H < G Cohen and Welling [2016a]. This means that the features of the layer / have shape [H] x o that is, of channels of dimension H For each layer I, we keep the total number of features (approximatively) constant when changing the group H. Models are trained until 99% of the training set is correctly classified with at least a margin 7y. We used = 10 in the synthetic datasets and 7 = 2 in the image ones.
First, we compare our result with the bound derived in Supplementary using naive application of Neyshabur et al. (2018). In Fig. and Fig. 3 we compare these two bounds on 6 synthetic datasets with (2) and (2) symmetries (one per column). Fach dataset lives on high dimensional tori and O(2) (or S0())) rotates the circles composing them, with different frequencies. We consider
8

---

Freq. F=1
Freq. F=2
Freq. F=3
Freq. F=4
Freq. F=5
Freq. F=6
15
[H]
Bound
0.10
0.08
12
Group
0.04
Generalization Error
Figure 3: Comparison between Theorem the synthetic S2( datasets.
(Ist row) and the one in Supplementary 11
(2nd row) on
different maximum frequencies F E (1,2..... in the experiments. For example, in Fig. 2 the first plot the left corresponds to synthetic dataset with ((2) symmetry generated only using frequency 1. See Supplementary
[1. for more details and visualization of the synthetic data.
The results in Fig. 2 and
S indicate that the bound built using the strategy from Neyshabur et al. 2018 cannot explain the effect of equivariance on generalization. Conversely, the bound in Theerrm 4. which uses the parametrization in the Fourier domain, correlates with the measured generalization error, suggesting that can account for the effect of different groups on generalization. In addition, note that it also correlates with the saturation effect observed when using larger discrete groups H to approximate the continuous group G O(2). Indeed, on low frequency datasets, the bound tends to saturate faster larger group results in larger improvements in the estimated bound.
increase the group size H Conversely,
high frequency datasets, choosing
Remark 5.1. As it can be seen in our experiments in Fig 2 and our bound is larger that the one in Neyshabur al. [2088) This is partially due to coarse approximation of Frobenius norm and the presence of the term 1 in our bound. This dependency could be alleviated if we increase the number of used irreps in the group convolutional network, namely the larger group size. It is an interesting research direction to explore the optimal dependency on the width for equivariant networks.
In Fig. 4 perform a larger study the transformed MNIST datasets to investigate the simultaneous effect of the group size [H). data augmentation and training set size m. For each training data size, the generalization eтror improves with larger equivariance group H.
We study the relation between the term E, MML, 1)) and the generalization error observed. Note that this term depends only on the architecture design, i.e. it is data and training agnostic. In Fig. 5] we show the correlation between these two quantities for two synthetic datasets. Both datasets have G = (2)) symmetry, but the data rotates with frequencies up to F in the first case and / in the second. We observe that the term E: / /M. 11) correlates strongly with the generalization in the high-frequency dataset (F 6), where the generalization benefits from increasing the size of the equivariance group. Conversely, in the low-frequency case (F = =), we observe a saturation of the performance, as increasing the group size does not improve generalization. In this setting, the term E, / (1, is only weak predictor of generalization. From these observations, interpret this term as an indicator of the expressiveness of a model. Particularly, when the irreps are chosen compatible with the dataset symmetries, the term E: / (I, provides a good guideline for the architecture choice. However, similar general neural networks, the generalization error dependent on other factors as well, which can be for example norms of network weights.
Conclusion
We provided learning theoretic frameworks to study the effect of invariance and equivariance on the generalization error and provide guidelines for design choices. The obtained bounds provide

---

0.8
GE
GE 0.7
GE
0.0
0.5
0.2
m
6000
m
6000
m
6000
[H]
[H]
[H]
(a) H Hx SO
(b) H = - G= ((2)
H= G=
0.8
0.8
0.0
GE
GE
GE
0.4
0.4
0.2
0.2
2000
2000
2000
4000
4000
4000
6000
20
6000
20
6000
40
[H]
[H]
[H]
(d) 11 Cv. G G0OO
(e) IT G= (2) (augment)
(1) == DN. G= ( (augment)
Figure 4: Generalization Error (GE) of different H -equivariant models (H = Cn or = Dx) on
different G-MNIST datasets (G SO( or G O(2)) for different training set sizes m.
5000
4000
MML m)
n)
3000
32
2000
16
12
2000
12
16
1000
30C
Group
1000
Group
Cu
0.32
Generalization Error
Generalization Error
(a) G O2),, Frequency
(b) G O(2), Frequency
Figure 5: Correlation between the term Σ, / (1,, n) and the Generalization Error (GE) different
H Heequivariant models (H C. or H = x) on the synthetic O(2) dataset with frequency F = and F 6, with a training set size m 3200.
useful insights and guidelines for understanding these architectures. As limitation of our work, show experimentally in supplementary materials that the obtained bounds do not decrease with larger training sizes m expected. Nevertheless, for fixed training set, the trend of the generalization bound correlates with the generalization error.
10

---

References
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger Generalization Bounds for Deep Nets via a Compression Approach. In International Conference on Machine Learning, pages 254-263, 2018.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky, Spectrally- normalizee margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6240-6249. Curran Associates, Inc., 2017.
Erik J Bekkers. B-spline CNNs on lie groups. In International Conference Learning Representa- lions, 2020.
Erik J. Bekkers, Maxime W Lafarge, Mitko Veta, Koen A.J. Eppenhof, Josien P.W. Pluim, and Remeo Duits. Roto-translation covariant convolutional networks for medical image analysis. In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), 2018.
Alberto Bietti and Julien Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. J. Mach. Learn. Res., 20(1):876-924, January 2019, ISSN 1532-4435.
Felix Biggs and Benjamin Guedj. Vacuous Generalisation Bounds for Shallow Neural Networks. 22Xiv:2202.01627 [cs, stat], February 2022. httgatppp//aarii..rr//////220000 2202.01627.
arXiv:
Gabriele Cesa, Leon Lang, and Maurice Weiler, A program to build e(n)-qquivariant stcerable CNNs. In International Conference on Learming Representations, 2022. URL https:///pennrevier
nett/foruu?.d--WAAeeet..
Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. drXiv:1602.07576 [cs.
stat], February 2016a. arXiv: 1602.07576.
Taco S. Cohen and Max Welling, Steerable CNNs. In ICLR 2017, November 2016b.
Taco S. Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant CNNs on homogeneous spaces. arXiv preprint 1Xiv:1811.02017, 2018.
Michaël Defferrard, Martino Milani, Frédérick Gusset, and Nathanaël Perraudin. DeepSphere: graph-based spherical CNN. In International Conference on Learning Representations, 2019.
Sander Dieleman, Jeffrey De Fauw, and Koray Kavukcuoglu. Exploiting cyclic symmetry in convolu- tional neural networks. In International Conference on Machine Learning (ICML), 2016.
Gintare Karolina Dziugaite and Daniel Roy. Entropy-SGD optimizes the prior of PAC-Bayes bound: Generalization properties of Entropy-SGID and data-dependent priors. In International Conference on Machine Learning, pages 1377-1386, July 2018a
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1008, 2017.
Gintare Karolina Dziugaite and Daniel M. Roy. Data-dependent PAC-Bayes priors via differential privacy. In Advances in Neural Information Processing Systems, pages 8430-8441, 201 8b.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, loannis Mitliagkas, and Daniel M. Roy. In search of robust measures generalization.
Advances in Neural Information Processing Systems, 33:11723-111
2020.
Bryn Elesedy. Group symmetry in PAC learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, page 9, 2022.
Bryn Flesedy and Sheheryar Zaidi, Provably striet generalisation benefit for equivariant models, In International Conference Machine Learning, pages 2959-2969. PMLR, 2021.

---

Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data. In International Conference on Machine Learning, pages 3165-3176. PMLR, 2020.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian learning of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 353-360, 2009.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-Independent Sample Complexity of Neural Networks. In Conference On Learning Theory, pages 297-299, July 2018.
Yiding Jiang. Behnam Neyshabur, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Fantastic Generalization Measures and Where to Find Them. In International Conference on Learning Representations, 2020.
Frederic Koehler, Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. Uniform Convergence of In- terpolators: Gaussian Width, Norm Bounds and Benign Overfitting. In Advances in Neural Informa- lion Processing Systems, May 2021. URL
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning (ICML), 2018
John Langford and John Shawe-taylor. PAC-Bayes Margins. In Advances in Neural Information Processing Systems 15. Citeseer, 2002.
Dmitry Laptev, Nikolay Savinov, Joachim M Buhmann, and Marc Pollefeys. Ti-pooling: transformation-inaaiini pooling for feature learning in convolutional neural networks. In Pro- ceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 289-297, 2016.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 28(5):1302-1338 October 2000. ISSN 0090-5364, 2168-8966. doi: 10. 10.12144 12//os/ 1015957395. Publisher: Institute of Mathematical Statistics.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In 35th AAAI Conference on Artificial Intelligence, pages 8279-8287 AAAI Press, 2021.
Philip M. Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. 1905v [cs, math, stat], May 2019. arXiv:
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.00/78 2020.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65 (10):133- 2012.
David A. McAllester. Some PAC-Bayesian Theorems. In Machine Learning, pages 230-234. ACM Press, 1998.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain gener- alization in deep learning. In H. Wallach, H. Larochelle, A. Beygelzimer, d'textquutesingle Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 11615-11626. Curran Associates, Inc., 2019.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel M. Roy. In Defense of Uniform Convergence: Generalization via derandomization with application to interpolating predictors. Technical Report arXiv:1912.04266 arXiv, September 2021. http:/ttt:///axx.. http///axivv... org/ http//b//1999 1912. 1912.04265.....1
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian Approach to Spectrally-Normaiized Margin Bounds for Neural Networks. In International Conference on Learning Representations, 2018.
12

---

Konstantinos Pitas, Andreas Loukas, Mike Davies, and Pierre Vandergheynst. Some limitations of norm based generalization bounds in deep neural networks. arXiv:1905.09660 (es, stat], May 2019. arXiv: 1905.09677.
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. arXiv preprini arXiv:2002.02912. 2020.
Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group invariant/equivariant deep networks via quotient feature spaces. In Uncertainty in Artificial Intelligence, pages 771 771-780. PMLR, 2021.
Jean-Pierre Serre. Linear representations of finite groups. Springer, 1977.
J. Shawe-Taylor. Building symmetries into feedforward networks. In 1989 First IEE International Conference on Artificial Neural Networks, (Conf. Publ. No. 313), page 158-162, Oct 1989.
J Shawe-Taylor, Symmetries and discriminability in feedforward network architectures. IEEE Trans. Neural Netw., page 1 1-25, 1993. ISSN 1045-9227.
John Shawe-Taylor and Jeffrey Wood. Representation theory and invariant neural networks. Discrete Applied Mathematics, 691)3))33,6 August 1996. Publisher: North-Holland.
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization Error of Invariant Classifiers. In Artificial Intelligence and Statistics, pages 1094-1103, 2017a.
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Robust Large Margin Deep Neural Networks. IEEE Transactions Signal Processing, 65(16):4265-4280, August 2017b. ISSN 1053-587X. doi: 10.1109/TS2:011:2700033
Nathaniel Thomas, Tess Smidt, Steven M. Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation- and translation-equiiariaat neural networks for 3d point clouds. arXiv preprint arXiv: 2018.
Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012.
Guillermo Valle-Pérez and Ard A. Louis. Generalization bounds for deep learning, December 2020. URL
arXiv:2012.04115 [cs, stat].
Gal Vardi, Ohad Shamir, and Nathan Srebro. The Sample Complexity of Onn-Hiideen-aaee Neural Networks. arXiv:2202.06233 [cs, stat], February 2022. URL httl:tttt///iii/// wwwpaaiwwi..aaaaaaaaaaaa org/abs/2202
06233
Colin Wei and Tengyu Ma. Improved Sample Complexities for Deep Networks and Robust Classifi- cation via All-Layer Margin. arXiv:1910.04286 [cs, stat], October 2019. arXiv: 1910.04284.
Maurice Weiler and Gabriele Cesa. General Equivaaaat Steerable CNNs. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco S. Cohen. 3D steerable CNNs: Learning rotationally equivariant features in volumetric data. In Conference on Neural Information Processing Systems (NeurIPS). 2018a
Maurice Weiler, Fred A. Hamprecht, and Martin Storath. Learning steerable filters for rotation equivariant CNNs. In Conference Computer Vision and Pattern Recognition (CVPR), 2018b.
Maurice Weiler, Patrick Forré, Erik Verlinde, and Max Welling. Coordinate Independent Convolu- tional Networks-Isometn and Gauge Equivariant Convolutions Riemannian Manifolds. arXiv preprint wrx.iv22066060020 2021.
Jeffrey Wood and John Shawe-Taylor Representation theory and invariant neural networks. Discrete Applied Mathematics, 69(1):33 60, 1996. ISSN 0166-218X. doi: https://doi.org//0.. 1016/
0166-218Xx99900075-3
13

---

Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow. Harmonic networks: Deep translation and rotation equivariance. In Conference on Computer Vision and Pultern Recognition (CVPR), 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR 2017, 2017.
Sicheng Zhu, Bang An, and Furong Huang. Understanding the Generalization Benefit Model Invariance from Data Perspective. In Advances in Neural Information Processing Systems, 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [No] The code and
the data are proprietary
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We have scatter plots of points from each run.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "o9hJG9BZ-bi", "reviewer": "Reviewer_fd7r", "summary": "The authors provide a generalization bound for a class of equivariant neural networks. The generalization bound extends prior bounds in the PAC Bayes literature. The prior PAC Bayes bounds were achieved by applying perturbations to weight matrices and studying the overlap of the posterior with the prior in the standard PAC Bayes setting. Here, perturbations are applied to parameters in the Fourier regime, which is parameterized much more sparsely than the real regime due to properties of linear equivariant layers as a consequence of Schur's Lemma. Their results indicate that the generalization bound they construct scales better with \"group-related\" parameters and may help explain generalization for invariant and equivariant models. ", "questions": "- Have the authors compared to existing generalization bounds for CNNs? This could be a nice empirical analysis to compare to a special case of equivariant models.\n- Are the y-axis values in figure 1 and figure 2 interpretable in any way. It seems that the complexity quantity is actually an order of magnitude or more smaller for the non-equivariant bound. Perhaps constant factors are not included here? This is concerning if the authors are trying to argue that the equivariant generalization bound outperforms the non-equivariant one it is inspired from.\n- I assume results here only hold for finite groups? If so, this should be stated explicitly.\n- Do bounds here inherently rely on invariance in the underlying model class one wants to learn? For example, if the final layer is fully connected making the network not invariant to the group action, does the bound suffer?\n- From my understanding, it seems the bound is stronger when the dimension of an irrep in the parameterization is large and the multiplicities are small. Is this correct? On a related point, when all mulitplicities are $1$ and all irreps are dimension $1$ like in standard convolution over cyclic group, is there any advantage to the proposed bound in theorem 4? It seems that case reduces to the Neyshabur et al. bound as far as I can tell. If so, this would be nice to point out for intuition. Also, it would be interesting to explore whether architectures used in practice actually follow this type of structure.", "limitations": "All limitations are stated in other parts of this review.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I was asked to review this paper under short notice and only over a couple of days; therefore, I was only able to read through the main paper. Proofs and mathematical details were not checked. \n\nOverall, I commend the authors for taking on the task of obtaining generalization bounds for equivariant neural networks. A theoretical understanding of GCNNs is mostly lacking and the results here would take a relatively big step in helping to explain why generalization occurs. The results are definitely new and interesting, but I fear at times the organization and presentation of the paper lets it down. In the short time I had to review this paper, I struggled to understand the main theorem enough to really analyze it in full. The notation and basic setting also took too long for me to comprehend. The mathematical results in this paper are potentially very strong, but I think the authors need to re-organize and write the paper more cleanly for the insights to come through. For this reason, I slightly lean towards rejecting the paper, but welcome a discussion from the authors. Since I only have had a very short time to review this paper, I am open to changing my mind.\n\nStrengths:\n- Generalization bounds, specifically for GCNNs, are hard to find. I, at least, am not familiar with any that specifically look at the architectures the authors analyze. To me, this is an original contribution of the authors' paper.\n- It can be challenging to analyze GCNNs theoretically since the group equivariance property adds yet another constraint to the theoretical analysis. The overall framework and mathematical tools the authors use to attack the problem may be applicable beyond the specific problem of generalization that the authors study.\n\nWeaknesses:\n- As a general point, there is little in the way of examples or intuition in this paper. The formula for the generalization bound is quite long. To add onto this, there are multiple norms within the generalization bound which can be challenging to understand even for readers who are familiar with GCNN literature. Comparing this to the bound in the Neyshabur et al. paper, it seems the major difference is in the Frobenius norm term with the dimension of the irrep dividing this factor. Is there anything else that has changed significantly? Is there a simple example where the authors can mathematically show their bound improves upon the Neyshabur et al. bound? For example, what happens with the cyclic group where we know all irreps are dimension 1? \n- After reading through the choice of equivariant neural network in section 3.2 (and a brief foray into appendix B), it took me a very long time to understand the setup of the basic equivariant layer. As I understand, the authors chose the given parameterization to be as general as possible with their equivariant layer. However, it is very challenging to understand this parameterization without digging into the details of the appendix. It would be nice if this part of the paper were self-standing and a visual example would help greatly to understand notation. \n- It seems that the equivariant parameters here are taken in Fourier space. This may be needed for proofs but as far as I can tell, this is only way to parameterize layers and not necessarily the most common. For example, even in standard convolution (i.e. over cyclic group), filters are parameterized over a sparse set of local elements. This is not necessarily \"easy\" to reconstruct in the Fourier domain as it would require enforcing parameter sharing across frequencies (i.e. just training over parameters in Fourier space will break the locality). Resulting perturbations to obtain generalization bounds may also ignore this locality in this case as enforcing perturbations in Fourier regime will not maintain the locality of the filter. The authors should at least comment on this point and be clear about the parameterization and its relevance to the models used in practice. This, after all, has obvious implications on generalization.\n\n\nSmaller comments:\n- The authors should at least state one commonly used architecture which follows the parameterization that they have selected both to aid intuition and to better ground the findings. \n- Figure 3 is hard to read. The font size is very small and the 3-D plots are hard to follow.\n- Similarly, figure 2 is quite crowded and in need of simplification and larger font.\n- Line 188: [18] should be [7]?\n- Line 240: section reference ??\n- Line 218: two periods\n- $\\beta$ in equation 12 is raised to the power $2L$ but then in the definition of $\\beta$, it is taken to the power $1/L$. Why not just ignore the added $L$ factor?\n\n\n\n\nMy recommendations to the authors on how to make the paper more readable:\n- Adjust section 3.2 to make it clearer how equivariant operations are parameterized. Start from basic definitions of convolution (e.g. in Fourier or real regimes) and then explain how the parameterization that they choose is equivalent to a specific parameterization in the Fourier or real regime. Give an example of an existing architecture to aid intuition. State whether parameterization in the form analyzed can be restricted locally (e.g., restricting to sparse set of irreps is not necessarily equivalent to a sparse real support as stated earlier). Some of the information currently there can be relegated to appendix (e.g. only look at $c_\\psi=1$ case and relegate rest to appendix).\n- Provide intuition behind the generalization bound by perhaps bounding further parameters or looking at a special case where some of the terms become constant. E.g. fix a certain number of layers and then look at the dependence on the other parameters.\n- Figures are too crowded right now. it is hard to read any of the figures as they stand and they take up too much space. I would have preferred to have more details on the architecture used to train networks and how that architecture varied for the various points in the figures. Also, a more complete description of how the comparison bound was calculated would be helpful. \n\n\n\n---\n**Post-feedback changes** \nI am upgrading my score to a weak accept after the authors' valuable update to the paper and their comments to my feedback. I still have some concerns about the presentation of the paper and the limitations which I have listed in my response to the authors' comments below. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M714yrsOe4c", "reviewer": "Reviewer_9Pp5", "summary": "This paper studies the generalization bounds of equivariant networks using the PAC-Bayes framework. The principal contribution of this work is an extension of the generalization bound from Neyshabur et. al 2018 to incorporate equivariant architectures by leveraging group and representation theory which allow the authors to characterize the bound using irreducible representations and their multiplicities. The authors also provide an empirical investigation of their generalization bounds on synthetic datasets as well variations of the MNIST dataset.", "questions": "From a technical point of view, the authors primarily work with $\\rho_{\\text{reg}}$ in the experiments which amount to the use of group convolutions as in Cohen et. al 2016. How does the current generalization theory change when we move to Steerable G-CNNs that $\\textit{do not}$ use these representations but are built using say irreps, quotient reps, etc ... Secondly, another important symmetry group for ML purposes is $\\mathcal{S}_n$ which is the symmetric group on $n$-elements. These can be used to define general permutation equivariant networks [1]. Can the authors bridge how their theory applies to these networks?\n\n\n[1] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In\nICLR, 2019", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main enjoys many strengths, the first of which is that the main contribution is presented in a clear and coherent way. Characterizing the generalization properties of equivariant networks is both an interesting direction and a needed one as the role of symmetry as powerful inductive biases are missing in the generalization literature. The main theorem and surrounding lemmas seem to be correct---although I did not check the technical details of Theorem 4.4 for correctness in the appendix as I did for the lemmas---and provide a sharp reduction in the hypothesis space and thus give tighter bounds. \n\n\nThe main weakness of this paper is that it seems that the authors missed the page limit for this year's NeurIPS is 9 pages and the current draft of the paper is considerably shorter (7.5 pages roughly). This is problematic because there are certain areas in the writing which could benefit from more detail. Chief among these is the experimental section, the plots in Fig 1 and 2 are incomprehensible and their explanations in the text don't add important details. For example, it seems row 2 in Fig 1 has a smaller generalization bound but the caption says that this is the bound obtained from a naive application by Neyshabur et. al 2018? There are also minor grievances that add to an overall lack of polish such as Equation 18 referenced in the main text to be an inequality is not the correct one being referenced in the appendix. There are also broken references (e.g. line 240 in the main text) and minor grammar mistakes all over. Given the additional page limit I encourage the authors to do the following, expand the experiment section and add more clarity. Add the details or bound of Appendix E to the main text as a way to contrast the tighter bound derived in the main text. Finally, provide a better proof sketch of the main theorem to the main text as much of the detail is completely committed (e.g. $\\eta$ is not defined in the theorem). My current score is a reflection of the current status of this paper which appears to be a bit rushed and not complete. If the authors can adequately improve upon these the score may change accordingly.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lhk3ELwBWY9", "reviewer": "Reviewer_MbmP", "summary": "This work introduces a novel PAC-Bayes bound for equivariant networks in which the feature transformation is determined in terms of groups irreps.  \nThe authors propose experiments in which the bound is shown to correlate with the generalization error, and the effect of group size, multiplicity and degree of the layers’ irreps is studied. ", "questions": "I wonder if the assumption of homogeneity is too restricive. Can a bound be derived while relaxing this condition?\n\nI would invite the authors to include some more relevant literature in their related work section. For instance:\n“Generalization bounds for deep learning”, Valle-Perez and Louis and reference therein.", "limitations": "The authors point out that, experimentally, their bounds do not decrease with the size of the training size, a fact that should be actually expected. Do the authors have a theoretical explanations/hypothesis for it? ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper, despite the technical nature of the topic, is mostly clearly written. The assumptions are clearly stated and the proofs in the appendix relatively easy to follow, although I did not check every single step. The paper addresses an interesting topic, that is, the derivation of PAC-Bayes bound for equivariant networks. \n\nI find it relatively hard to understand the motivation behind some technical assumptions (see section below for an example) about the setting for proving the theorem. I would appreciate if the authors could provide some more motivation behind their choices, or highlight choices that are made purely for a technical standpoint (i.e., it is possible to prove).\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G0wWG4Iaqs", "reviewer": "Reviewer_rgnq", "summary": "This paper gives generalization bounds on equivariant models for general groups.\nGeneralization bounds for equivariant models in the case of finite groups were given by Sannai et al. but generalization bounds for general groups were not known. The boundary is described by an invariant called multiplicity.\nThis attempt is new to the best of my knowledge.\n", "questions": "According to Sannai et al. the generalization gap is obtained by the number of coverings of the quotient space for the group action. Can you see that it is tighter than its bounds?", "limitations": "Properly addressed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The author should first note and cite that generalization bounds are given for finite groups by Sannai et al.\n\nStrengths\nThis paper differs from Sannai et al. in that it deals with equivariant models that are not limited to finite groups.\nFurthermore, the bounds in this paper use information on the multiplicity of irreducible representations used in the model. This is commendable.\n\nWeaknesses\nOn the other hand, the right-hand side still has some parts that have not been fully calculated, such as multiplicities.\nAs it is, I do not believe that any useful findings have been obtained.\nOverall, the results are not considered significant.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept