On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing
Authors: Arash Behboodi
Gabriele Cesa
Venue: Accepted by TMLR ()

Abstract: Weight sharing, equivariance, and local filters, as in convolutional neural networks, are believed to contribute to the sample efficiency of neural networks. However, it is not clear how each one of these design choices contributes to the generalization error. Through the lens of statistical learning theory, we aim to provide insight into this question by characterizing the relative impact of each choice on the sample complexity. We obtain lower and upper sample complexity bounds for a class of single hidden layer networks. For a large class of activation functions, the bounds depend merely on the norm of filters and are dimension-independent. We also provide bounds for max-pooling and an extension to multi-layer networks, both with mild dimension dependence. 
We provide a few takeaways from the theoretical results. It can be shown that depending on the weight-sharing mechanism, the non-equivariant weight-sharing can yield a similar generalization bound as the equivariant one.
We show that locality has generalization benefits, however the uncertainty principle implies a trade-off between locality and expressivity. We conduct extensive experiments and highlight some consistent trends for these models.

Published in Transactions on Machine Learning Research (01/2025)
On the Sample Complexity of One Hidden Layer Networks with Equivariance, Locality and Weight Sharing
Arash Behboodi Qualcomm AT Research
behboodi wttp:/:ww.ggllooooooooo
Gabriele Cesa Qualcomm AI Research"
goesalutti qwwlcquaa.ccoo
Reviewed on OpenReview: https: // openreview. net/ formfo id- Q7aXOnBGgU
Abstract
Weight sharing, equivariance, and local filters, as in convolutional neural networks, are believed to contribute to the sample efficiency of neural networks. However, it is not clear how each one of these design choices contributes to the generalization error. Through the lens of statistical learning theory, we aim to provide insight into this question by characterizing the relative impact of each choice on the sample complexity. We obtain lower and upper sample complexity bounds for a class of single hidden layer networks. For a large class activation functions, the bounds depend merely on the norm of filters and are dimension- iindiiioonndeeedee... We also provide bounds for max-pooling and extension to multi-layer nelworks, both with mild dimension dependence. We provide few takeaways from the theoretical results. It can be shown that depending on the weight-sharing mechanism, the non-cquivariant weight-sharing can yield a similar generalization bound as the equivariant one. We show that locality has generalization benefits, however the uncertainty principle implies a trade-off between locality and expressivity. We conduct extensive experiments and highlight some consistent trends for these models.
1 Introduction
In recent years, equivariant neural networks have gained particular interest within the machine learning community thanks to their inherent ability to preserve certain transformations in the input data, thereby providing form of inductive bias that aligns with many real-world problems. Indoed, equivariant networks have shown remarkable performance in various applications, ranging from computer vision to molecular chemistry, where data often exhibit specific forms of symmetry. Equivariant networks are closely related to their more traditional counterparts, Convolutional Noural Networks (CNNs). CNNs are a particular class of neural networks that achieve equivariance to translation. The convolution operation in CNNs ensures that the response a particular feature is the same, regardless of spatial location in the input data. However, equivariance extends beyond just translation, accommodating broader spectrum of transformations such rotations, reflections, and scaling. Group Convolutional Neural Networks (GCNNs) Cohen and Welling (2016a) are the typical example of equivariant neural networks. The inductive bias rntrodeed by equivariance, in the form of symmetry preservation, offers an intuitive connection to their generalization capabilities. By encoding prior knowledge about the structure of the data, equivariant networks can efficiently exploit the inherent symmetries, reducing sample complexity and improving generalization performance. This ability to generalize from a limited set of examples is crucial their success. Their mathematical foundation is grounded in group representation theory, which provides a powerful framework to understand and design neural networks that. equivariant invariant, to the action of group of Lransformations.
*Qualcomm AT Research is intiative of Qualcomm Technologies, Inc.

---

Published in Transactions on Machine Learning Research (01/2025)
Besides the inductive bias of data symmetry, the generalization benefits of CNNs and GCNNs are additionally attributed to the weight-sharing implemented by the convolution operation and the locality implemented by the smaller filter size. In this paper, we study the impact of equivariance, weight-sharing, and locality on generalization within the framework of statistical learning theory. Our focus will be on ncural networks with one hidden layer. Similar to works like Vardi et al. (2022); Magen and Shamir (2023), we believe that, this study provides a first step toward a better understanding of deeper networks. Getting dimension-free generalization error bounds constitutes an important line of research in the literature. Following this line of work, we provide various timension-free and norm- based bounds for one hidden layer networks. See Appendix J. for discussions on the desiderata of learning theory.
Contributions. We consider class of one hidden layer networks where the first layer is a multi-channel equivariant layer followed by point-wisc non-lincarity, a pooling layer, and the final linear layer. We assume that the 22-norm of the parameters of each layer is bounded. For architectures based on group convolution with point-wise non-linearie linearierrty we provide generalization bounds for various pooling operations that are entirely dimension-free. We obtain a similar norm-based bound for general equivariant networks. We also provide a lower bound on Rademacher complexity that shows the tightness of our bound. We extend the results max-pooling, combining various covering number arguments for Rademacher complexity analysis. The bound is only dimension-deeenderr on the number of hidden layer channels and logarithmii-dependendt on the group size; otherwise, it is independent of other dimensions. We also extend the result to multi-layer networks and discuss its limitations. We show that no gain is observed if the analysis is conducted for the networks parameterized in the frequency domain. When a layer replaces the equivariant layer with, not necessarily equivariant, weight-sharing, we also provide a dimension-free bound. By studying the bound, it can be seen that some particular weight-sharing schemes, although not all, can provide similar gencralization guarantees. Next, we give another bound for networks with local filters and show that the locality can bring additional gain on top of cquivariance. We will then show trade-off between locality in the spatial and frequency domains, which is important for band-linited inputs. The uncertainly principle characterizes the trade-off. Finally, we provide the numerical verification of our bounds. The generalization bounds are all obtained using Rademacher complexity analysis. We relegate all proofs to the appendix.
Notations. We introduce some of the notations used throughout the paper. We define [n] := {I....,. n for n E W. The term ||-|| refers to the fz-norm, which for the space of matrices is the Frobenius norm. The spectral norm of a matrix is denoted by ||A||| 12122-12-
positively homogeneous activation function a(...) is a function that satisfies oAxz) = (z) for all X 2 0. The loss functions are assumed to be I-Lipschitz. The matrix of the training data is denoted by X [x1... ... r..)- The terms C(h) and ((h) denotes, respoctively, the test and the training error.
2 Preliminaries
Convolution: a simple example. We start with a simple example of familiar convolutional neural networks, indulging some of the subtleties needed for our later discussions. For an RGB image input, each convolution filter will slide over the input image and act on its receptive field by simple multiplication. If we translate the pixels of the input image, ignoring the corner pixels, the output of the previous convolution operation would just get translated as well. The act of translation is an example of a group action, and the fact that this act shifts the convolution output is an example of equivariance property In what follows, we work with a generalized notion of action captured by group theory, which studies objects like translation and rotation that can combine and have an inverse element.
We introduce key concepts from group and representation theories necessary to present our main results in A Appendix A Tn the rest of this work, we will generally assume a compact group G. Note that this includes any finite group. For the most part, we will consider Abelion groups, i.e., commutative groups (such as planar rotations or periodic translations).
We would like to emphasize again that the example is not perfect. First, the convolution in CNN is cross-correlation. Second, the conventional CNNs are only approximately translation equivariant because of the finite input size and the corner pixels.
2

---

Published in Transactions on Machine Learning Research (01/2025)
Group convolution with chhhnnels::
with eychnnnels
(A)
x(0)
output sychenmels
x(Fu)
c(1,co)
W
y())
x(I)
((1.1)
((Ge))) 1)
y())
Pooling
Final oulput
TCL
X
y
Weight sharing with sychennets:
Locality with Og receptive field size:
v0
Wun 0020 (120
x()
Summary of Impacts on the goneratization orror
Group convelution with cychnnnels: tactor (1) M4l100
yhy (x(())
Weight sharing with sychennels: factor
B
the (x(())
x
(K30
Bi
Pu.u
(x(()
X
Locality with Og racaptivn field size: nize: foctor
Learnable weight
Foad matricss
Each patch (u(x(0) has O2 element
Figure 1: Visualization of the network architectures with equivariance, locality, and weight sharing. On the right, also summarize how each choice impacts the generalization error in our theory.
Given two spaces X, carrying an action of a group G, a function o X' + y is said to equivariant with respect G ((g.z) g.o(x) for any x E X, i.c. á commutes with the group's action. For example, the spaces X could be vector spaces, and the group action G G X X' could be linear function.
Equivariance.
Group Convolution. If G is a finite group, the most popular design choice to construct equivariant networks relies on the group convolution operator Cohen and Welling (2016a), thereby generalizing typical convolutional neural networks (CNNs). Specifically, given an input signal æ G + R over and a filter w G + R. the group convolution produces another output signal y + R defined as:
v (w @G ()) Σ wlg wh)())))(h)) h))(h)
(1)
REG
Note that the signals x, w can be represented vectors w. y E BIG; hence, the convolution operation can be expressed as y Wæ, where W e IR G] x|G] is group-circulan matrix encoding G-convolution with the filter w.
Like in classical CNNs, one typically considers multi-channel input signals x + R filters w - Xox and output signals y G R9 We represent a multi-channel signal x G 18 as stack of features over the group G, namely, tensor (a=1),.... ((()),),,,((())) of shape |G] co (i.c. with channels and each ==1) R ). Then, convolution layer consists of convolutional filters {wy.j [cı]], each of size |G] co, parametrized by per-channel convolutions ((.)) E TR. Gl i [co]: the convolution operation, which yields the output channel
j, is given by
ca
æ())
Σ W.D @G x(1) E HRG.
[c]]
In summary, group convolution layer can be visualized as
Wen
Was Wan
Worn (on
201 & RIMI
9(1) R
Was
x(2) & RIOT
v(2) E R
(2)
W Wiae
Wizen
M R9
3

---

Published in Transactions on Machine Learning Research (01/2025)
Here, any W(.)) R block is a group circulant matrix corresponding to G, which encodes G- convolution paramcterisod by a filter Wi.j E IR GI Note that the output of the convolution is a |G] x or signal, i.e. contains a different value y( for each group element g E G and output channel j E [ci]-
Note also that the group G naturally acts Then, one can show that the group convolution operator above is equivariant with respect to this action on its imput and output, i.e., w @g g.z - g-(w @a 2))). Additionally, it is well known, e.g,- Cohen et al. (2018); Kondor and Trivedi (2018), that group convolutions with learnable filters in this form parameterize the most general linear equivariant maps between feature spaces of signals over a compact group G. Finally, GCNN typically uses an activation function applied point-wise on the convolution output. In our 1-layer architecture, first convolution layer is followed by a pointwise activation layer and, then, per-channel average or max- pooling layer, which produces e₁ invariant features. These final features are mixed with the final linear layer u. See Figure | for more details. The final network is then given as:
signal x : G - R g 2:zz 9.2, with [g.a](h) 2(g hh).
Cn ((.))) @G @G x(1)
Li=1
( = u Poo
(3)
co (c.,)) @a x(1))/
where P(.) is the pooling operation, and w == (111)))))t is the concatenation of all kernels.
3 Related Works
Equívariant and Geometric Deep Learning Previous works attempted to improve machine learning models by loveraging prior knowledge about the symmetrics and the geometry of problem [Bonstein et al.
(2021) A variely of design stralegies have been explored in the liverature to achieve group equivariance, for
Finzi et al. (2021), group convolution Cohen and Welling (2016a); Kondor and Trivedi (2018); Bekkers et al. (2018) Lie group convolution Bekkers (2020);
example via equivariant MLPs (ShawehTaaaal 19933
1989];
Finzi et al. (2020), steerable convolution Cohen and Welling (2016b Cohen el al. (2018): ; Worrall el al.
(2017): : Weiler et al. (2018b Thomas et al. (2018); Weiler and Cesa ): Fuchs et al. (2020): Brandstetter
et al.) (2021); Cesa et al. (2022) and, very recently, by using geometric algebra Ruhe et al. (2023): Brehmer
et al. )023), to only mention a few. Other previous approaches include Mallat (012); Dieleman et al. (016));
Defferrard et al. (2019). Some of these ideas have also been used to generalize convolution beyond groups to
more generic manifolds via the framework of Gauge equivariance Cohen et al. (2019); Weiler et al. (2021)
While equivariance is generally considered a powerful inductive bias that improves data efficiency, this large selection of equivariant designs raises the following question: What impact do different architectural choices have on performance, and to what extent do they aid generalization?
Generalization Properties of Equivariant, networks Some previous works t.ridd to answer some aspects of this question. SSyllr (1991) is one of the first works studying the relation between invariance and generalization. For example, (Sokolić et al. (2017a) extend the nobustness-baset generalization bounds found in Sokolić et al. (201 by assuming the set of transformatioos of interest change the inputs drastically, thereby proving that the generalization eтror of a G-invariant classifier scales L/v[Gl, where |G] is the cardinality of the finite equivariance group G. Bietti and Mairal (2019) study the stability of some particular compact group equivariant models and also describe an associated Rademacher complexity and generalization bound. Lyle et al. (2020) investigate the effect of invariance under the lenses of the PAC-Bayesian framework but do not provide an explicit bound. Later, [lesedy and Zaidi (2021) use VC-dimension analysis and derive more concrete bounds. Elesedy (2022) studies compact-gront equivariance in PAC learning framework and equates learning with equivariant hypotheses and learning on reduced data space of orbit representatives to obtain a sample complexity bound. Sannai et al. (2021) propose a similar idca, proving that equivariant models work in a reduced space, the Quolient Feature Space (QFS), whose volume directly affects the generalization error. While the result relaxes the robustness assumption in (Sokolić et al. (2017a), the final bound is suboptimal with respect to the sample size. PAC lcarnability under transformation invariance is also studied in (Shao et al. (2022). Zhhu et al.) (2021) characterize the generalization benefit of invariant models using an argument based the covering number induced by a set of transformations. More recently, Behboodi et al. (022) leverages
4

---

Published in Transactions on Machine Learning Research (01/2025)
ropresenttttion-thooeette construction of equivariant networks and provides a norm-based PAC- PAC-Bayesian generalization bound inspired by Neyshabur et al. (2018). Finally, Petrache and Trivedi (2023) considers a more general setting, allowing for approximate, partial, and misspecified equivariance and studying how the relation between data and model equivariance error impacts generalization.
Generalization in generic neural networks Many works in the literature have previously investigated the generalization properties of deep learning methods. [hhang et al. (2017) first noted that a model trained random labels can achieve small training errors while producing arbilrarily large generalization errors. This result raised a new challenge in the field since popular uniform complexity measures such VC dimensions are inconsistent with this finding. This inspired many recent works which tried to explain generalization in terms of other quantities, such as margin or norms of the learnable weights; a few non-exhaustive examples
are Wei and Ma (2019): Sokolić et al. (2017b); Neyshabur et al. (2018); Arora et al.
(2018): Bartlett et al.
2017); Golowich
al. (2018); Dziugaite and Roy] (2018a); Long and Sedghi (2019) Vardi et al. (2022);
Ledent et al. 2022 ); Valle-Péred and Louis (2020). The PAC Bayesian framework is a particularly popular
method. It has been applied to neural networks in many previous works, e.g. see Neyshabur et al. (2018)
Biggs and Guedj )022]; Dzingaite and Roy (2017 2018b a); Dziugaite et al. (0200) Lotfi et al. (2022). Jiang
et al. (2020) perform a thorough experimental comparison of many complexity measures and identifies some
failure cases; see also Nagarajan and Kolter (2019); Koehler et al. (0021); Negrea et al. (2021) for further
discussion on uniform complexity measures and their limitations. The norm based bounds can still be tight and informative for shallow networks considered in this work.
Generalization bounds for Convolutional neural networks As one of the most popular deep learning architectures, convolutional neural networks (CNNs) have received particular attention in the litcrature. Generalization studies on CNNs are especially relevant for our work since we focus significantly on equivariance to finite and abelian groups, which can often be realized via periodic convolution. Pitas et al. (2019) Long
and Sedghi (2019); Vardi et al. (2022): Ledent et al. (2021) previously studied these architectures. The authors in Vardi et al. (2022) represented a convolutional layer as a linear layer applied on local patches and used Rademacher complexity to get the bound. Tn Long and Sedghi (209)), the bound is derived using Vapnik- Chervonenkis analysis Vapnik and Chervonenkis (2015): Giné and Guillou| (2001) and depends on the number of parameters but independent of the number of pixels in the input. In Graf et al. (2022), the authors use two novering-numbers-baee bounds for Rademacher complexity analysis of convolutional models. Please see Appendix for further discussions.
4 Sample Complexity Bounds For Equivariant Networks
We consider the group convolutional networks as defined in eq. 3 We assume that the input to the network is bounded as ||>||| by P Consider the following hypothesis space:
H. == [hu, ||u||| < M1, ||w||| < M2}.
(4)
where u E R w E Reee [G], The hypothesis space is the group convolution network class that has bounded Euclidean norm on the kernels. For this network, we derive dimension-free bounds.
Since the pooling operation is a permutation invariant operation, we can use Theorem in Zaheer al. (2017) to show that one can always find two functions & R G|+1 R and p IR R such that P Poz z = à (1d) E!al p(zi)) We can provide the following generalization bound for subset of such representations, namely for positively homogeneous o: R - IR and p:R. P:R-
Theorem 4.1. Consider the hypothesis space H defined in eq. 4 If P(-) is the pooling operation represented as Poz øl Jे 1 p(z)), where the two functions pl-), o(-) and the activation function af-) are all 1 1-Lipschitz positively homogeneous activation function, then with probability at least 8 and for all h E H. we hove:
((h) < 2(h) +2 by M,
2log(4/8)
+ +4/
vm
m
Forr all the results in the paper, we can use data-dependent. bound the input. Namely, it suffices to assume that max ||æa||| S bg-
5

---

Published in Transactions on Machine Learning Research (01/2025)
The proof leverages Rademacher complexity analysis and is presented in Appendix C.5 Note that the assumption of positively homogeneity is only needed to utilize the peeling technique of Golowich et al. (2018). We expect that similar techniques from Vardi ct al. (0222) can be used to extend the result to Lipschitz activation functions.
Consider now the special case of average pooling operation P(æ) बि I x. This is linear layer; therefore, can be combined with the last layer u to yield a standard two-layer neural network. We can utilize the results from Vardi et al.] p2022p; Golowich et al. (2018). The combination of the layer u and average pooling is lincar layer with the norm M1/ //// and the matrix W, circulant matrix, has the Frobenius norm /IG M2. The product of these norms would be bounded by M Being a special case of the model in Vardi al. (2022), we can use their results off-the-shelf to get an upper bound on the sample complexity that depends only on M,Ms M2 for Lipschilz-accliaaiion functions (Theorem of Vardi el al. (2022)) )) We provide independent proof for positively homogeneous activation functions in Appendix C.2 with a clean form. Note that the authors in Vardi et al. (2022) provide result for average pooling that contains the term Os,, the maximal number of patches that any single input coordinate appears. In our case, this term equals |G), which is canceled out by the average pooling term. Their bound depends on the spectral norm of the underlying circulant matrix, which can be bigger than the norm of the filter provided here. But, their proof can be reworked with the norm of convolutional filter instcad, in which case, their result will be our special case.
Average pooling.
Impact of group size. The above theorem is dimension-free, and there is dependence on the number of imput and output chamnels and C1. as well as the group size [G]. Note that for average pooling and sufficiently smooth activation functions, we can use even the stronger result (Theorem 4 of Vardi et al. (2022) and get a bound that depends on M, / VIG,, where M2_2 is the spectral norm of W. This manifests the impact of group size on the generalization similar to Sokolić et al. (2017a); Behboodi et al. (0022).
Max pooling. We cannot rely on the previous rosults for the max pooling operation since the peeling argument would not work. Theorem 7 and 8 of Vardi et al. (2022) provide bound for max pooling, however their network does not contain the linear aggregation u after max-pooling, and their bound contains dimension dependencies such as log(GGla, or log(m). We provide various bounds for max pooling in Appendix C.3 and
C.4 The proof technique different from the above results. Again, the bounds have different dimension dependencies. We believe these dependencies are proof artifacts. Removing them would be an interesting direction for future work.
To summarize, we have established that for single hidden layer group convolution network, we can have dimension-free bound that depends merely the norm of filters.
Remark 4.2 (Frequency Domain Analysis). The authors in Behboodi et al. (2022) improved the PAC-Bayesian generalization ion bound by conducting their analysis using the representation in the frequency domain. In our Rademacher analysis, such a shift. would not bring any additional gain, and recover the same bound. We provide the details in the supplementary materials.
4.1 Bounds for Multi-Layer Equivariant Network
In this section, we study simple extension to multi-layer group equivariant networks. Consider the following network with L hidden layer:
(w (((L)) (
(5)
where P(.) is the average pooling operation, a-)) is the ReLU function. Each linear layer W is the same the mapping in eq. 2 but with q-1 and a as the input and output channels. The new hypothesis space is given by:
( = (hu,(w(,,eldd) |||||| S M1. |wsl|| S M441 E [L]}.
(6)
We have the following theorem.
6

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 4.3. Consider the hypothesis space HI) defined in eq. all h E H, we have:
6
With probability at least 1 - ô and for
[(h) - [(h) - bz bz|Gi + M2 ML+1
2 llg
+ 4/
Vm
m
The proof can be found in Appendix C.6
We first comment on the dimension dependency of the bound. Although our bound has no dependence on the number of input and hidden layer channels, it still has dependence on (G)(2-1)/2 It is not entirely dimension-froe. Using some other techniques, for example, see Section 3 in Golowich et al. (2018), can be improved to (L 1) log |G] for 1. However, dimension dependence is only concern of the above result. It is worth pointing out that the generalization bounds for deeper networks suffer from many shortcomings and generally fail to correlate well with the empirical generalization error. For example, various norm bounds were considered in Jiang et al. (2020), and the correlation with the generalization error was explored. Generally, the norm-based bounds performed poorly, while sharpness- aware bounds showed promises. Besides, in Nagarajan and Kolter (2019), the norm-based bounds were shown to increase drastically with the training set size, leading looser bounds with incrcasing training set size. Therefore, think these norm-based bounds have limitations in deep net generalization analysis.
4.2 Lower bound on the Rademacher Complexity Analysis
A natural question that might come up whether the obtained bound is tight or not. this section, we provide an answer this by showing that the Rademacher complexity lower bounded similarly for class of networks.
Theorem 4.4. Consider the hypothesis space H defined eg. 4 If P(.) is the average pooling operation, and o-) the ReLU activation function, then there is a data distribution such that the Rademacher complezity is lower bounded by cbndd,As where is an independent constant. vm
The proof is provided in the Appendix Note that Rademacher complexity (RC) bounds are known to be tight for shallow models, such as SVMs. Indeed, if one fixes the first layer and only trains the last linear layer with weight decay, the model is equivalent to hard-margin SVM, for which RC bounds are tight. We also provide additional evidence in the numerical result section.
5 General Equivariant Networks
The focus of our analysis in the above section has been on group convolutional networks and related architectures. In particular, we had considered the equivariance for finite Abelian groups for which the filters were implemented using multi-channel convolutio operation. We now look the general equivariant networks w.r.t. a compact group. As we will see, the analysis for these networks would be based on their MLP structure.
We follow the procedure described in Cohen and Welling (2016b); Cesa et al. 2022 Weiler et al. (0018b) We assume a general input space where the action of the compact group G on the space is given by lincar map Po(g) for E G. For this space, the filters of the first layer, similarly to GCNs, are parametrized in the frequency domain. The generalization of Fourier analysis to compact groups is done via the notion of irreducible representations (irreps). An irrep, typically denoted by v, can be thought as a frequency component of a signal over the group.
Using tools from the representation theory, the map Po(g) be represented in the frequency domain as the direct sum of irreps QT {+ Di +b) w) )oQ Qo where mo is the multiplicity of the irrep vb The matrix Qo is a unitary matrix representing the generalized Fourier transform given by a = Qoæ. See Appendix A.1] for detailed definitions. similar frequency domain representation can be obtained for the hidden layer in terms of irreps, each with multiplicity m1,6- The block diagonal structure of filters in the multi-channel GCNs given in eq. 33 is now obtained by general block-diagonal structure. The equivariant neural network is
7

---

Published in Transactions on Machine Learning Research (01/2025)
represented
Weipe ma.ei
h M.W w = a Q20
Q
Σ ((b.i.)) _=1
Since we are working with the point-wise non-lincarity a the spatial domain, two unitary transformations QI and Q2 are applied Fourier transforms from the frequency domain to the spatial domain. The last. layer û should be chosen to yield group invariant function, which means that the vector ú only aggregates the frequencies of the trivial representation to, and it is zero otherwise. To use analogy with group convolutional networks, Q1 and Q2 are the Fourier matrices, and à is a combination of the pooling, which projects into the trivial representation of the group, and the last aggregation step. The general equivariant networks are defined in Fourier space as follows:
Haww (aa.w || S M1. | s M2
Note that the hypothesis space assumes bounded norm of the filters' parameters in the frequency domain. For this hypothesis space, we can get a similar dimension-freo bound.
Thcorem 5.1. Consider the hypothesis space Ha, of equivariant networks with bounded weight norms. If the activation function o(-) is 1-Lipschitz positively homogeneous, then with probability at least 1 ô for all E Hi we have:
L(h) - ((h) + b. M1 + + llog(4/0)
Vm
The proof is presented in Appendix D networks that depend merely on the norm of the kernels. Note that the network has a standard MLP structure, so the result can be obtained using techniques used in Golowich et al. (2018). Also, note that constructing equivariant networks in the frequency domain is useful in steerable networks to deal with continuous rotation
This result provides another dimension-free free bounds for equivariant
groups Poulenard and Guibas 2021
Cesa al. 2022 while the parametrization in the spatial domain is
pursued in works like Bekkers (2020)
Finzi et al. (2020).
6 Generalization Bounds for Weight Sharing
In this section, we try to answer the question whether the gain of our bound lics in the specific equivariant architecture or weight sharing. The answer subtle. Indeed, an arbitrary lype of weight sharing will not bring out the generalization gain. However, weight-sharing schemes can lead a similar gain without necessarily being equivariant.
For fair comparison with the group convolution network explained above, consider architecture with the same number of effective parameters shared similarly. The weight-sharing network is specified as follows:
Σe
1 (k) x<c)
w (1.0)
h n (x: = u TPoo
Eee
[IIG] u (e (k) xx(c)
where B&'s are fixed |G] x G matrices inducing the weight sharing scheme. These matrices are not trained using data and merely specify how the weights are shared in the network. For example, if B, 's are chosen the basis for the space of circulant matrices, the setup boils down to the group convolution network.
The corresponding hypothesis space is defined as:
H.w.. = (x) ||w||| < M1, ||w// S M
where
|wwl := max
Σ
w (io) (k)
se[[G]]
cE(eo)JE(e.)
8

---

Published in Transactions on Machine Learning Research (01/2025)
The following proposition provides purely norm-based generalization bound.
Proposition 6.1. For the class of functions h in the hypothesis space H with the average pooling operation P, a.)) as 1-Lipschitz positively homogeneous activation function, the generalization error is bounded as:
Dz M
2 1og(4/6)
[(h) - ((h) +2
+ 4
Vm
Note that if by.'' 's are the rows of the circulant matrices, then we end up with the same result as before with Mg = M2. Interestingly, if the vectors {bx,1 k E [[G]]] 's are orthogonal to each other for each 1 E [[G]], and all of them have unit norm, i.c., ||b,,]|| = 1, then we also get M = M2. The conclusion is that the weight sharing can impact the generalization similarly to the group convolution, even the construction does not arise from the group convolution. This does not generally hold, particularly the row vectors of matrices B₃ not orthogonal. Note that throughout the paper, have not assumed anything regarding the underlying distribution, which can be without symmetry. On the other hand, the gain of equivariance shows itself for distributions with built-in symmetries if we assume that the underlying task has invariance equivariance property.
7 Generalization Bounds for Local Filters
In previous sections, we observed that the impact of equivariance the generalization is very similar to that of weight sharing under an appropriately chosen basis. Another argument relates the generalization benefits of convolutional neural networks to the use of local filters, where the same filter is applied to number of patches. The patches have lower dimensions, and the filters similarly have lower dimensions than the total input dimension. Note that this goes beyond the benefit of weight sharing mentioned in the previous section. One example is Theorem in Vardi et al. (2022); we follow their setup. In their case, each convolution operation ((.k) @G zkk) can be represented the patch 1. Each patch selects subset of input entries. The patches &- {Φr, 1 E [[G]]] are assumed to be local, in the sense that each coordinate in xkk appears at most in Op mumber of patches with O2 < |G), More formally, for any vector x and a set 5 C [[G]], define the vector æs = (æ,)res, i.c., with entries selected from the index S. Define the patch di : RIG + R.d as (1(x)) = æs for a subset St. The group convolution network with locality is defined as:
(WT.A (( ... (.,) (za()) where Φr(-) represents
E m (a
Nu,
(x) = uu Too
E k=l
(w)
By reorganizing the weights in each row corresponding to each patch, the whole network is presented as u P o where we assume that the matrix W conforms to the set patches &. The hypothesis space with locality defined as H u (x)) ||u||| < Mi, |/w/|| S M2).
For this class of functions, can be shown that there is generalization benefit in using local filters besides the gain of equivariance proper weight sharing. This conclusion is captured in the following result.
Proposition 7.1. Consider the hypothesis space of functions 7t constructed by patches Φ the average pooling operation P, 1-Lipschitz positively homogeneous activation function a. Let Os be the maximal number of patches that any input entry appears in. Then, with probability least 1 - 8 and for all & E H we have:
Oo M,
2 (og(4/))
C(h) < ((h) +//
+ 4
G
Vm
m
9

---

Published in Transactions on Machine Learning Research (01/2025)
Compared with the result above, the locality assumption brings an additional improvement of Ig Although the proof focuses on average pooling and group convolution, the same results can be obtained for weight sharing. We should only change the filter paramctrization from the matrix By basis to the vector basis b given as
[ |G| k= (0),,)(())
The architecture considered in Vardi et al. (2022) is a single-channel version of our result (see more discussions in Appendix J In that case, the difference in their bounds is in using the spectral norm of W. However, their proof only needs a bound on the Euclidean norm of weights, which would end in the same result as ours.
The analysis so far has focused on the local filters in the spatial domain. However, the filters are also applied per frequency in the frequency domain and are, therefore, local. This can be seen from the block diagonal structure of filters (D, (v))). In this sense, the filters in the frequency domain are already local. When the filters are band-limited in the frequency domain, we have an additional notion of locality. In practice, this is useful when the input is also band-limited; therefore, not all the frequencies are useful for learning. This introduces a fundamental trade-off for locality benefits arising from the uncertainty principle Donoho and Stark 1989 : Folland and Sitaram 1997). According the uncertainty principle, the band-limited filters with B non-zero components will have at least |G|/B non-zero entries in the spatial domain (sce Section I for more details). The trade-off is captured in the following proposition.
Proposition 7.2. Consider the hypothesis space of group convolution networks with band-limited filters. If the filters have B non-zero entries in the frequency domain, then the generalization error term in Proposition 7.1 for the smallest spatial filters is at least of order O(b, M2/VmB)
As it can be seen, the assumption of band-limitedness can potentially bring the gain of order 1/B if the filters are spatially local. To summarize,, there is a gain in using local filters. However, since band-limited filters are more efficient for band-limited signals, the uncertainty principle imposes minimum spatial size for band-limited filters.
8 Numerical Results
Let us first introduce the two family of groups we consider in our experiments: the cyclic group Cn containing n discrete rotations and the dihedral group D,, of n discrete rotations and reflections (see Def. A.2 and Def. A.3 for precise definitions of these groups).
In this section, we validate our theoretical results on variation of the rotated MNIST and CIFAR10 datasets where we consider a simpler binary classification task (determining whether a digit is smaller or larger than 4 in MNIST and whether an image belongs to the first 5 classes of CIFARIO or not). Rather than working with raw images, we pre-process the dataset by linearly projecting each image via a fixed randomly initialized G sst-steeaa convolution layer Weiler and Cesa 2019 to a single 6400-dimensional feature voctor interpreted for a visualization of this linear projection. When constructing equivariance to a subgroup G < Daz, this feature vector is interpreted as Co 100 [Dazl -channels signal over G. We design our equivariant networks as in Eq. 3 and use C1 . |G x 2000 total intermediate channels for all groups G in the MNIST experiments and C G 4000 in the CIFARI0 ones. The dataset is then augmented with random D32 transformations to make it symmetric. Hence, we expect that G-equivariant models with G closer to Dx2 to perform best.
Co 100-channels signal over G= Dx2; see Appendix K for more details and Fig. 5
In these experiments, we are interested in how well our theoretical bound correlates with the observed trends. In particular, we focus on the M, term which is the main component in our bounds. In Fig 2 we evaluate ymm
the networks on different values of training set size and different equivariance groups G. We first observe that the M, term correlates well with the empirical generalization error on both the MNIST dataset in m
Fig. 2a and the CIFAR10 dataset in Fig. 2c In particular, larger groups G achieve both lower generalization error and lower value of our norm bound. We also note that this term decreases as 1/ V in Fig. 2b which
This is random linear transformation of the input images into feature vectors: the reader can think of this as analogous to reshaping an image before fooding it into an MLP, but with some care to preserve rotation and reflection equivariance. Note also that, since the output (6400) much larger than the number of input pixels, this transformation is practically invertible and preserves all relevant. imput information.
10

---

Published in Transactions on Machine Learning Research (01/2025)
leg/Si
lngiFi
35
30-
3.0
25-
2.5
MyM,
MyM;
2.0
15-
1.5
ERIANNC 300
GIICON DOUR
0.05
0:10
0.15
0.20
0.25
1000
2000
3000
4000
5000
6000
Generalization Error
(a) Generalization error vs our bound on MNIST
(b) Our bound vs number of samples on MNIST
log/Gi
logici
1.0
1.0
MM
0.6
M,M;
0.6
10
Du
0.2
0.2
0.0
0.50
0.05
6110
6.15
0.20 0.25 0:30 0.35
5000
10000
15000
20000
25000
Generalization Error
(c) Generalization error bound CIFAR1O (d) Our bound number of samples CIFAR1O
Figure 2: Numerical results for the generalization error on the rotated MNIST and CIFAR10 datasets. The plots on the left, (a)-(c), confirm that our thcoretical bound captures the effect of different configurations: equivariance groups G, training set sizes and datasets on the generalization error, i.e. there is positive correlation between the generalization error and our theoretical bound Mi Ma across all these cases. On the right, (b)-(d), we verify the bound decreases following a trend similar training set sizes m.
1 and approaching zero for large Vm
indicates that our bound becomes vacuous as increases, and we do not suffer from deficiencies of other norm based bounds Nagarajan and Kolter (2019).
Overall, these results suggest that our bound can explain generulization across different choices of equivariance group G, as well as different training settings.
Next, we investigate how other oquivariant design choices affect generalization and verify our bound can model this effect. Precisely, when parameterizing the filters over the group G in the frequency (i.e. irreps) domain (as in Sec 5), it is common to only use smaller subset of all frequencies. A bandlimited sub-set of frequencies can be interpreted as form of locality in the frequency domain, in analogy to the local filters in Sec 7 In 3 we experiments on CIFAR10 with different variations of our equivariant architecture obtained by varying the maximum frequency used to parameterize filters. Tn these experiments, we keep the training dataset size fixed to m = 3200 and we only consider the largest groups (since a wider range of frequencies in N/2] can be chosen).
In Fig 3 find that our bound caplures the effect of locality in the frequency domain on the generulization.
11

---

Published in Transactions on Machine Learning Research (01/2025)
Our bound vs. the general- ization error on CIFAR10 (training set size m 3200) when varying the max- imum frequency used to parameterize the filters, which is the locality effect in the frequency domain. Each dot and its error bars represent the mean and standard deviation over least runs with the same configuration. As expected, architectures leveraging lower frequency design achieve lower generlization error and our bound can exactly caplure this effect. Note that increased frequencies are still benefi- cial for the final test performance: we study the trade-off between generaliza- tion and test performance as function of the model frequency in Fig.
Figure 3:
C16
D16
0.25
Max Freq.
0.20
vm
0.15
0.05
G C32
= Dsz
0.25
0.20
0.10
0.05
0.05
0.10
0.15
0.05
0.10
0.15
Generalization Eror
Generalization Error
Fig. we observed that higher frequencies typically lead to worse generalization. For this reason, we inchude final study to explore the effect of locality in the frequency domain i..., fand-limitation on the final test performance of the models and the associated trade-offs between generalization and expressivity. Fig. compares the generalization error with the final test accuracy of some of our models when varying the maximum frequency of the filters and the training set size This visualization highlights particular behavior: low-frequency models tend to achieve lower generalization error because of worse data fitting (lower test accuracy). Conversely, higher frequency models often show higher generalization errors (especially in the low data regime) but achieve much higher test performance. Moreover, high-frequency models benefit the most from increased datasel size m. These properties lead to the (multiple) V-shaped patterns Fig. 4 on the smaller datasets (light dots in Fig. 4 while increasing frequencies leads improved test accuracy, it also increases the generalization error. On the other hand, in the larger dataset (dark dots in Fig. 4 higher frequencies directly improve the lest performance and even show minor improvements in generalization iiaiiiiiziio error. When varying dataset size, these different behaviors form multiple V-shaped patterns in Fig. (highlighted with the dotted lines).
Figure 4: Test accuracy vs. Generalization егтоr on CIFAR10 when varying the marimum frequency used to paramcterize the filters and the training set size m. Each dot the aver- age performance over at least 3 runs with the same configuration. In Fig. g found that higher frequencies correlated with higher gen- eralization error: here, study the trade-off between generalization and test performance. For each dataset size m, increasing the fre- quency improves the test performance until a certain saturation point; beyond that, in- creased frequencies mostly lead to increased generalization error. We highlight this effect by drawing four dotted lines following the trends for varying frequencies with G = C2z on four different dataset sizes m: the different slopes the curves correspond to the different saturation effects.
Cit
0.64
Test Accuracy
0.62
log
10
0.60
11
12
13
0.58
Max Frea
0.58
G = Cs
D
12
15
Accuracy
0.62
0.60
0.50
0.56
Generallzation Error
Generalization Emrr
12

---

Published in Transactions on Machine Learning Research (01/2025)
8.1 Main Insights from Numerical Results
We would like to summarize some of the main insights from the numerical examples, some of which pose interesting theoretical questions.
The gencralization error seems to be lowest at the medium group sizes as seen in MNIST or CIFAR experiments, although the Irend unclear. There seems be a group size that leads to the lowest generalization error, and if this conjecture is correct is an open question.
The other observation is about the relation between test accuracy and the generalization error. In general, it can be seen that the highest test accuracies have lower generalization errors in all the plots in Figure D Tt. is interesting to directly explore the impact of the group size on the test error, which requires different. machinery.
9 Conclusion
In this work, we provided various generalization bounds on equivariant networks with single hidden layer as well as a bound for multi-layer neural networks. We have used Rademacher complexity analysis to derive these bounds, where the proofs were based on either direct analysis the Rademacher complexity or covering number arguments. The bounds are mostly dimension- dimensions. They only depend the norm of learnable weights. The situation changes for multi-layer scenarios and max-pooling where some dimension dependency appears in the bound. In light of the results the limitation of uniform complexity bounds for deeper neural networks Nagarajan and Kolter (2019); Jiang et al. (2020), we believe that the bound on multi-layer scenario would suffer from similar limitations. However, the emergence of some dimensions in the bound for max-pooling seems related to how covering number argument was applied. Whether the dependency can be removed for max-pooling an interesting research direction.
as they do not depend on the input and output
We have considered equivariant models spatial and frequency domains, models with weight sharing, and local filters. The first insight from analysis is that suitable weight-sharing techniques should be able to provide similar guarantees. This is not surprising, as we did not assume any symmetry in the data distribution. Other works in the literature have highlighted the benefit of equivariance if such symmetries exist see, for example, Sannai et al. (2021); Sokolić et al. (2017a). Finally, local filters can potentially provide an additional gain, although the story for band-limited filters more subtle. We also provide a lower bound on Rademacher complexity. We have conducted extensive numerical experiments and investigated the correlation between our generalization error and the true error, well as the relation between the number of samples, group size, and frequency.
We have focused on positively homogencous activation functions. We expect that the result can be extended to general Lipschitz activations using techniques in Vardi et al. (2022). However, the current proof techniques would not work for form-based nonlinearities used in equivariant literature Worrall et al. (2017): Weiler et al. (2018a); Weiler and Cesa (2019). We encourage readers to consult Appendix for comparison with other works and future directions.
13

---

Published in Transactions on Machine Learning Research (01/2025)
References
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger Generalization Bounds for Deep Nets via a Comprossion Approach. In International Conference on Machine Learning, pages 254-263, 2018.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3(Nov):463-45 482, 2002.
Peler L. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spertrallyy-oormaiized 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.
Arash Behboodi, Gabriele Cesa, and Taco S. Cohen. A pac-bayesian generalization bound for equivariant networks. Advances in Neural Information Processing Systems, 35:5654-5666 2022.
Erik Bekkers. B-spline CNNs on lie groups. In International Conference on Learning Represenlations, 2020.
Erik J. Bekkers, Maxime W Lafarge, Mitko Veta, Koen A.J. Eppenhof, Josien P.W. Pluim, and Remco Duits. Roto-translation covariant convolutional networks for medical image analysis. In International Conference on Medicol Image Computing and Computer- Assisted Intervention (MICCAI), 2018.
Alberto Bictti 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. Non-Vacuona Generalisation Bounds for Shallow Neural Networks. arXiv: 2202.
arXin:2202.016 (es, statj, February 2022. URL
Johannes Brandstetter, Rob Hesselink, Elise van der Pol, Erik J Bekkers, and Max Welling. Geometric and physical quantitics improve (3) equivariant message passing. arXiv preprint SSS::21100000000 2021.
Johann Brehmer, Pim De Haan, Sönke Behrends, and Taco Cohen. Geometric algebra transformers. arxiv preprint XrXi::235.. 18415, 2023.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 19478, 2021.
Gabriele Cesa, Leon Lang, and Maurice Weiler. A program to build e e(n)-equivariant steerable CNNs. In International Conference on Learning Representations, 2022. URL https://ppenrrviei.nettt///// fot/oommii
NE4ge9xIn0w/
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge oquivariant convolutional networks and the icosahedral enn. In International conference on Machine learniing, pages 1321 1330. PMLR, 2019.
Taco S. Cohen and Max Welling. Group Equivariant Convolutional Networks. February 2016a. arXiv: 1602.07576.
[cs, stat],
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. ar preprint ftt::1111.00011 2018.
Michaäl Defferrard, Martino Milani, Frédérick Gusset, and Nathanaäl Perraudin. DeepSphere: a graph-based spherical CNN. In International Conference on Learning Representations, 2019.
Sander Dieleman, Jeffrey De Fauw, and Koray Kavukcuoglu. Exploiting cyclic symmetry in convolutional neural networks. In International Conference on Machine Learning (ICML), 2016.
David L. Donoho and Philip B. Stark. Uncertainty Principles and Signal Recovery. SIAM Journal on Applied Mathemalics, 49(3):906 991, June 1989. ISSN 0036-1399, 1095-712X.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Gintare Karolina Dziugaite and Daniel Roy. Entropy-SGD optimizes the prior of PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors. In International Conference on Machine Learning, pages 1377 1386, July 2018a.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous gencralization bounds for deep (stochas- tie) neural networks with many more parameters than training data. arXiv preprinl arxiv 103. 10008 2017.
Gintare Karolina Dziugaite and Danicl M. Roy. Data-dependent PAC-Bayos priors via diffcrential privacy. Advances in Newral Information Processing Systems, pages 8430 8441, 2018b.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M. Roy. In search of robust measures of generalization. Advances in Neural Information Processing Systems, 33:11723 11733, 2020.
Bryn Elesedy. Group symmetry in PAC learning. In ICLR 2022 Workshop on Geomelrical and Topological Representation, Learning, page 9, 2022.
Bryn Elesedy and Sheheryar Zaídi. Provably strict generalisation benefit for equivariant models. In International Conference on 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 arbitrary continuous data. In International Conference on Machine Learning, pages 3165 3176. PMLR, 2020.
Mare Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups. In International conference on machine learning, pages 3318 3328. PMLR, 2021.
Gerald B. Folland and Alladi Sitaram. The uncortainty principle: A mathematical survey. The Journal of Fourier Analysis and Applicalions, 3(3):207 238, May 1997. ISSN 1069-5869, 1531-5851.
Simon Foucart and Holger Rauhut. Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Springer New York, New York, NY, 2013. URL httt:://iink springer
0om///001007//78----876---80
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se(3)-transformee 3d roto-translation equivariant attention networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1970 1981. Cur- ran Associates, Inc., 2020. URL
pdf
Evarist Giné and Armelle Guillou. On consistency of kernel density estimators for randomly censored data: rates holding uniformly over adaptive intervals. Ann. Inst. Henri Poincare Probab. Stat., 37(4):503-522 522, August 2001.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Indeennneen Sample Complexity of Neural Networks. In Conference On Learning Theory, pages 297-299, July 2018.
Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, and Roland Kwitt. measuring excess
capacity in neural networks. Advances in Neural Information Processing Systems, 35:10164-10178, 2022.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems, 31, 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.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Frederic Kochler, Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting. In Aduances in Neural Information 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 Machine Learning (ICML), 2018.
Hannah Lawrence, Kristian Georgiev, Andrew Dienes, and Bobak T Kiani. Implicit bias of linear equivariant networks. In International Conference on Machine Learning, pages 22096-1212,, PMLR, 2022.
Antoine Ledent, Walced Mustafa, Yunwen Lei, and Marius Kloft. Norm-based gencralisation bounds for deep multi-class convolutional neural networks. In 35th AAAI Conference on Artificial Intelligence, pages 8279 8287. AAAI Press, 2021.
Michel Ledoux and Michel Talagrand. Probabilily in Banach spaces: isoperimelry and processes. Classics in mathematios. Springer, Berlin; London, 2011. OCLC: ocn751525992.
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why Are Convolutional Nets More Sample-Efficien than Fully-Connected Nets? In International Conference on Learning Representations, 2021.
Philip M. Long and Hanic Sedghi. Sizc-free generalization bounds for convolutional neural networks.
urXiv:1905. 00.9905.26600 12600 [es, math, statj, May 2019. arXiv: 1905.12600.
Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapezynski, Micah Goldblum, and Andrew G Wilson. Pac-bayes compression bounds so tight that they can explain generalization. Advonces in Neural Information Processing Systems, 35:31459 31473, 2022.
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem- of invariance in neural networks. arXiv preprint arXiv:205..00 0015..01770 78, 2020.
Bloem-Reddy. Reddy. On the benefits
Roey Magen and Ohad Shamir. Initialiaatonn-Deeendnnt Sample Complexity of Linear Predictors and Neural Networks. In seirth Conference on Newrol Information Processing Systems, 2023.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10): 1331-1398, 2012.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. Adaptive Computation and Machine Learning series. MIT Press, London, England, 2 edition, December 2018.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' deteeqquoeesin Alché-Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages Associates, Inc., 2019.
Curran
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel M. Roy. In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors. Technical Report arXiv:1912.04266, arXiv, September 2021. URL http://arxiv. org/ /tab//92.... 04265
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. PAC-Bayesian Approach to Spectrally- Normalized Margin Bounds for Neural Networks. In International Conference on Learning Representations, 2018.
Mircca Petrache and Shubhendu Trivedi. Approximattoonggnerllaattoo trado-offs under (approximate) group cquivariance. arXiv preprint arXit:2305.11592, 2023.
G. Pisier. Remarques un résultat publié de B. Maurey, Seminar on Functional Analysis (Polytechnique), 13(5):1-12, 1980.
Gilles Pisier. The Volume of Conver Bodies and Banach Space Geometry. Cambridge University Press, edition, October 1989.
16

---

Published in Transactions on Machine Learning Research (01/2025)
Konstantinos Pitas, Andreas Loukas, Mike Davies, and Pierre Vandergheynst. Some limitations of norm based generalization bounds in deep neural networks. 1eXxx:105.00660 [es, statf, May 2019. arXiv: 1905.09677.
Adrien Poulenard and Leonidas J. Guibas. A functional approach to rotation equivariant non-linearities for tensor field networks. In 2021 IEEE/CVF Conference on Computer Vision and Pottern Recognition (CVPR), pages 13169-13178, 2021. doi:
David Ruhe, Johannes Brandstetter, and Patrick Forré. Clifford group equivariant neural networks. arXie preprint (xXt:2205.11144: 2023.
Sara Sabour, Nicholas Frosst, and Gcoffrey E. Hinton. Dynamic routing between capsules. Aduances in nearal informalion processing systems, 30, 2017.
Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group ceaariant/quivarrinn deep networks via quotient feature spaces. In Uncerlainly in Artificial Intelligence, pages 771-780. PMLR, 2021.
Jean-Pierre Serre. Linear representations of finite groups. Springer, 1977.
Shai Shalev-Shwarts and Shai Ben-David. Understanding machine learning: from theory to algorithms. Cambridge University Press, New York, NY, USA, 2014.
Han Shao, Omar Montasser, and Avrim Blun. A theory of pac learnability under transformation invariances. Advances in Newral Information Processing Systems, 35:13989-14001, 2022.
J. Shawe-Taylor, Building symmetrics into feedforward networks. In 1989 First IEE International Conference on Artificial Neural Networks, (Conf. Publ. No. 313), page 158 162, 10 1989.
Shawe-Taylor. Symmetrics and discriminability in foedforward network architectures. IEEE Trans. Neural Netw., page 1-25, 1993. ISSN 1045-9227.
John Shawe-Taylor Taylor Threshold network learning in the presence of equivalences. In J. Moody, S. Han- son, and R.P. Lippmann, editors, Advances in Neural Information Processing Systems, volume 4. Morgan-Kaufmann, 1991. URL ttctps://prooceddggs.eeeee wwtp.ipp..cppppprreaaeeeee fwl.fillespppppl /alles/paper/199//11ee// 087408522211e1111180000aaalal... Paoosff-aprrpppp
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization Error of Invariant Classifiers. In Artificial Intelligence and Statistics, pages 1094-1108, 2017a.
Jure Sokolíć, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Robust Large Margin Deep Neural Networks. TEEE Transactions on Signal Processing, 65(16):4265-4222 4280, August 2017b. ISSN 1053-587X. doi: D0.1009/TSPP2011.227700
Ingo Steinwart and Andreas Christmann. Support vector machines. Information science and statistics. Springer, New York, 1st ed edition, 2008.
Nathaniel Thomas, Tess Smidt, Steven M. Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tonsor field networks: Rotation- and translation-oquiiariant noural networks for 3d point clouds. arXic preprint arXiv:1802.082 08219, 2018.
Guillermo Valle-Pérez and Ard A. Louis. Generalization bounds for deep learning, December 2020. URL http://arxiv.org. arg/abs/2122 04115 arXiv:2012.04115 [cs, stat].
V Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Vladimir Vovk, Harris Papadopoulos, and Alexander Gammerman, editors, Measures of Complexity; Festschrift for Alexey Chervonenkis, pages 11 30. Springer International Publishing, Cham, 2015.
Gal Vardi, Ohad Shamir, and Nathan Srebro. The Sample Complexity of One-Hiiden-LLyer Neural Networks. arXiv:2202.062. 062333 fes, stat], February 2022. URL httt:://arrdv..orraaa/////a
17

---

Published in Transactions on Machine Learning Research (01/2025)
Zihao Wang and Lei Wu. Theoretical Analysis of Inductive Biases in Deep Convolutional Networks, May 2023. URT. http://arxiv... arg/abss22305.88444 arXiv:2305.08404 [es, stat].
Colin Wei and Tengyu Ma. Improved Sample Complexities for Deep Networks and Robust Classification via All-Tayer Margin. arXi::1900.044 (cs, statj, October 2019. arXiv: 1910.04284.
Maurice Weiler and Gabriele Cesa. General Equiivaqi Steerable CNNs. In Conference on Newral Information Processing Systems (NewrIPS), 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 (NewrIPS), 2018a.
Maurice Weiler, Fred A. Hamprecht, and Martin Storath. Learning steerable filters for rotation equivariant CNNs. In Conference Computer Vision and Pallern Recognition (CVPR), 2018b.
Maurice Weiler, Patrick Forré, Erik Verlinde, and Max Welling. Coordinate Independent Convolutional Networks-Isometry and Gauge Equivariant Convolutions on Riemannian Manifolds. ar preprint arXiv:2106.0008 2021.
Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetor, and Gabriel J. Brostow. Harmonic networks:
Deep translation and rotation equivariance. Conference on Computer Vision and Paltern Recognition (CVPR), 2017.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R. Salakhutdinov, and Alexan- der J. Smola. Deep Sets. Advances in Neural Information Processing Systems, 30, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR 2017, 2017.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 55Mar)5527-550, 2002.
Sicheng Zhu, Bang An, and Furong Huang. Understanding the Generalization Benefit of Model Invariance from a Data Perspective. In Advonces in Neural Information Processing Systems, 2021.
18

---

Published in Transactions on Machine Learning Research (01/2025)
A An Overview of Representation Theory and Equivariant Networks
We provide brief overview of some useful concepts from (compact group) Representation Theory in this supplementary section.
Definition A.1 (Group). A group a set G of elements together with binary operation G G + G satisfying the following three group axioms:
Associativity:
Va,b,cEG a. (.(b.) (a b)
Identily:
BeEG:VyEC g.e=e.g-g
Inverse:
Vg G e eG: g
g=
The inverse elements g 1 of an element 9, and the identity element are unique. Moreover, if the binary operation is also commutative, the group G is called abelion group. To simplify the notation, we commonly write ab instead of b.
The order of a group G is the cardinality of its set and is indicated by |G|. A group G is finite when |G| E N, i.c when has a finite number of elements. A compact group a group that is also a compact topological space with continuous group operation. Every finile group also compact (with a discrete lopology).
We now present two examples of finite groups that we used throughout our experiments, the cyclic and the dihedral groups.
Definition A.2 (Cyclic Group). The cyelic group ON of order N is the group of N discrete rotations by angles which are integer multiples of N ie. {Rp pe [0, (0,1....,N 1]}.
The binary operation combines two rotations to generate the sum of the two rotations. This is represented by integer sum modulo N, i.e.
R Rg
=Ripto mod N
Definition A.3 (Dihedral Group). The dihedral group DN of order 2N N is the group of N discrete 25 rotations (by angles which are integer multiples of N and N reflections (generated by reflection along an axis followed by any of the N rotations), i.e.
R Ipe 10.......... N UR F pe 10. N 11}
where F a reflection along an axis. Note that the group Dy has size 2N and contains the group On as a subgroup.
Another important concept that of group action:
Definition A.4 (Group Action). The action of a group G on set X' is map : x X X, (g. + g.
satisfying the following axioms:
identity: Vx E =
compatibility: ba G E (.b..) = (ab).
For example, group can act on functions over the group's elements: given a signal x G + R, the action of E G on x is defined as [g) == 1h), iee,, "translates" the function x.
The orbit of x E X' through G is the set G.r = {g.xlg E G). The orbits of the elements X' form partition of X. By considering the equivalence relation Vz, y E x NG y < G.y (or, equivalently, y E G.r), one can define the quotient space X/G (G.r X), i.e. the set of all different orbits.
19

---

Published in Transactions on Machine Learning Research (01/2025)
Definition A.5 (Linear Representation). Given group G and vector space V, linear representation of G is homomorphism p: G + GL((V) associating to each element of g E G an invertible matrix acting on V, such that:
Vg,h G, p(gh) = p(g)p(h).
T.e. the matrix multiplication (())p(h) needs to be compatible with the group composition gh.
The most simple representation is the trivial represenlation v G + R + 1, mapping all elements to the multiplicatiie identity E V R. The common 2-dimensional rotation matrices are an example of representation on V IR2 of the group SO(2):
(ro) cos sin 0
sin 0 cos with 0 2T). In the complex field C, circular harmonics are other representations of the rotation group:
(a((r)) = -ike V = C where & E Z is the harmonic's frequency. Similarly, these representations can be constructed also for the finite cyclic group CN Z/NZ:
(x(p) = e skk V =V= C²
with p (0, , N -
Regular Representation A particularly important representation is the regular representation Preg of a finile group G. This representation acts on the space V = TR |R| of vectors representing functions over the group G. The regular representation Preg(9 (g) an element g E is a |G| x GG permatation matriz. Each vector x = Gl can be interpreted as a function over the group, x : G - IR, with x(g;) being i-th entries of x. Then, the matrix-vector multiplication Preg(g) represents the action of g on the function which generates the 'translated' function g.v. These representations are of high importance because they describe the features of group convolution networks.
Direct Sum Given two representations P1 G - GL(R"*) and P2 G - GL(R"*), their direct sum Pi ① P2: G GL( representation obtained by stacking the two reprosentations as follows:
(pr 1 p2) = (p)(g) O
p2(g)
Note that this representation acts on 12 t2e which contains the concatenation of the vectors in R and R",, By combining copics of the regular representation via the direct sum, one obtains a representation of G acting on the features of a group convolution network with c channels.
Fourier Transform The classical Fourier analysis of periodic discrete functions can be framed as the rep- resentation theory of the Z/NZ group. This is summarised by the following result: the regular representation of G = Z/NZ is equivalent to the direct sum of all circular harmonics with frequency & E (0..... N 1}, i.e. there exists a unitary matrix F E CNN such that:
Proge (p) = F
(Walo)) F
+ (2(( A
for .O....,N- - Z2NNZ and where th is the circular harmonic of frequency k as defined earlier in this section. The unitary matrix F is what is typically referred to as the (unitary)discrele discrete Fourier Transform operator, while its conjugate transpose F is the Inverse Fourier Transform one.
By indexing the dimensions of the vector space CV on which Preg acts with the clements p E (O....,N N-13 of G Z/NZ, the Fourier transform matrix can be explicitly constructed as
FE.
1
vk(p) =
Rkp 2F
(8)
20

---

Published in Transactions on Machine Learning Research (01/2025)
One can verify that the matrix is indeed unitary.
In representation theoretic terms, the circular harmonics (Pa are referred to as the irreducible represen- tations (or irreps) of the group G = Z/NZ. While we are mostly interested in commutative (abelian) finite groups in this work, this construction can be casily extended to square-integrabl signals over non-abelian compact groups by using the more general concept of irreducible representations Behboodi et al. (2022): ; Cesa
al. 2022). See also Serre (977) for rigorous details about representation theory.
Notation Given signal G + C, typically write V CIG] to refer to the vector containing the values of at cach group element. Note that this is the vector space on which Preg acts We also use a = Fz to indicate the vector of Fourier coefficients and & to indicate the function associating to each frequency k (or, equivalently, irrep v/k) the corresponding Fourier coefficient. *(tb) E C.
Group Convolution Given a vector space associated with a representation p: G GL(V) of a group G, the group convolulion @G C G) of two elements x. E V is defined
Vg E G
(w @g (g) = w wf p(g)"
(9)
What defined is technically group cross-corrclation and it differs from the usual definitions of convolution over groups. We still refer to it as group convolution to follow the common terminology in the Deep Learning literature. One can prove that group convolution is equivariant to G, ie::
@g p(g) Preg(g) (w @g x))
If = Cla), then x, w. : + C can be interpreted as signals over the group, and group convolution take the more familiar form
(w @c <)) = Σ : ()(o)
(10)
AEG
Finally, we recall two important properties of the Fourier transform: given two signals w,r C, the following properties hold
-
= (1))(())
(11)
@G x(() (()))(()))
(12)
Eq. guarantoes that transformation by 9 of x does not mix the coefficients associated different irreps frepuuscis...cccs.... Eq. 12 is the typical convolution theorem.
Finally, some of these results related the Fourier transform generalized by the following theorems. This last property is related to the more general result expressed by Schur's Lemma:
Theorem A.6 (Schur's Lemma). Let G be compact group (not necessarily abelian) and t/ and the two irreps of G. Then, there exists a non-zero linear map W such that
Wi(g) -
for any g E G (i.e, an equivariant linear map) if and only if th and th2 are equivalent representations, í.e. they differ at most by a change of basis Q: v = Q+2(g)Q-1 for all g G.
A second result generalizes the notion of Fourier transform to representations beyond the regular one: Theorem A.7 (Peter- Peyter-Weyl Theorem). Let G be compact group and p unitary representation of G. Then, decomposes inlo direct sum of irreducible regresentations of G, up to change of basis, i.e.
p(g) = U
+
UT
Each irrep db can appear in the decomposition with a multiplicity my 0.
21

---

Published in Transactions on Machine Learning Research (01/2025)
In particular, in the case of regular representation, the change of basis is given preciscly by the Fourier transform matrix F.
The combination of these two results is typically used in steerable CNNs and other equivariant designs to characterize arbitrary equivariant networks by reducing the study to individual irreducible components. See also the next section.
A.1 Equivariant Networks
We now discuss some popular equivariant neural network designs.
In this work, we consider real valued networks with layers, i.c,, we limit our discussion to hypothesis class of the form
H. = fu f (Wx)).
a G-equivariant network, the group G carries an action on the intermediate features the model; these actions are specified by group representations, which we introduced in the previous section. We assume the action of an element g G on the imput and the output of the first layer is given respectively by the matrices po(g) and (1)).. The first layer, including the activation function, is equivariant with respect to G if:
Vg E G, oWW (()))a)) = (W()
Instead, the last layer of the network is invariant with respect the action of the group on the input data via Po. which means that:
G, u uWo(Wx) = =u ((())())())) = o ((WPolg)az
A typical way to construct networks equivariant which we introduced in the previous section; this is the Group Convolution neural network: (GCNN) design Cohen and Welling (2016a). Indeed, if the representation Pi is chosen to be the direct regular representation Preg of G, i.e. PI = + Preg and the input Pa θo0 Preg also consists of co copies of the regular representation, then the linear layer W can always be expressed as x group-convolution linear operators as in eq.
GCNNs
finite group is via group convolution,
of C1 copies of the
((.1)
W (2.1)
W 1))
W (1.2)
W (2.2)
W (c)
W
W ((Le))
W (2,c1)
W ((o.er)
where each W(,)) ((.) E [| G-circular matrix (i.e. rows are "rotations' of each others via prog) of the form:
w Th Prep)))))))1))
W (i.)) =
w Prez(99
In this case, note that the representation Pl acts via permutation and, therefore, any activation function o which is applied to each entry of Wæ entry-wise is equivariant: this includes the typical activations used in deep learning (e.g. ReLUU
General linear layer The representation theoretic tools we roduced earlier allow for a quite general framework to describe a wide family of equivariant networks beyond group- group-convolution by considering the generalization the Fourier transform we discussed in the previous section. By using Theorem A.7 a representation pi (for 0, decomposes into direct sum of irreps as follows:
mi,
= Ui
Vb
U..
1=1
22

---

Published in Transactions on Machine Learning Research (01/2025)
Activation function
Definition
Norm ReLU Weiler et al. (2018b); Worrall et al. (2017)
77( [c ReLU( x
(b < 0)
Squashing Sabour et al. (0017)
<][[==]])
Gated Weiler et al. (018b)
77
|
x
Table 1: Equivariant activation functions
where Uj is an orthogonal matrix, and my, is the multiplicity of the irrep si in the representation pt- If dimø is the dimensionality of the irrep e, the width of the network is equal to Ei, dimæ, and the input dimension d is given by E dim
Next, by combining this result with Theorem A.6 an equivariant network can be parameterized entirely in terms of irreps, which is analogous to a Fourier space parameterization convolutional network. Defining Wi U. WWU-,,, the oquivariance condition writes as
my 1.
|
mi
EgEG, Wi
θ
v01) =
(5)))
(0))
W..
This induces block structure in Wi, where the (v, ()) jj)tth block block maps the i-th input block transforming according to 1b to the j-th output block transforming under vi', with E [m- and j E [m, By Theorem A.6. there no linear maps equivariant to & and vf whenever these representations are in-equivalent; this implies the matrix Wi is sparse since its (1h, i; j))th block is non-zero only when v _ v³. Then, the non-zero (1, j,jht block (here, we drop the redundant v/ index) is denoted by (i,((bb and should commute with (g)) for any g E G. This is achieved by expressing this matrix as a linear combination of a few fixed basis matrices spanning the space; see Behboodi el. al. (2022) Cesa al. (2022) for more details.
In the special case of GCNN with abelian group G, each irrep in the intermediate features occurs exactly C times. Similarly, if the imput representation Po consists of co copies of the regular representation, each irrep appears exactly co times in po- Then, (vb) is the Fourier transform of the filter wi.j) [ at the frequency/rrrge vb.
Activation function a Each module in an equivariant network should commute with the action of the group on its own input in order to guarantee the overall equivariance of the model. Hence, the activation function a used in the intermodiate layer should be equivariant with respect to pı(g) as well, i..,, (p)()))) = (x)) Vy E G. Different activation functions are used in the literature. As we unitary representations, one use norm nonlinearities, (xx) = [][[==]] [لl for suitable function 17 E5 R It can be seen that (p) (g)x) = Pi (x)) Some examples are norm ReLU Worrall et al. (2017), squashing Sabour et al. (2017) and gated nonlinearities Weiler et al. (2018b).
As introduced in the GCNN paragraph, when the intermediate representation is built from the regular representation, any pointwise activation is admissible: since the group's action permutes the features' entries in the spatial domain, it intertwines with the non-linearity applied entry-wise. There exist also other type of activations, such as tensor-product non-linearities (based on the Mebsh- transform) but we do not consider them here
Last layer The last layer maps the features after the activation to single scalar and is assumed to be invariant. This linear layer can be thought of special case of the general framework above, with the choice of output representation P2 being collection of trivial representations, i.e., p2(g) is the identity. Since the trivial representation is an irrep, by Theorem A.6. this lincar map only captures the invariant information in the output of the activation function. In the case of a GCNN with pointwise activation this layer acts as an averaging pooling operator over the |G] entries of each channel and learns the weights to lincarly combine the e independent channels. Note that one can also include a custom pooling operator P(-) (e.g., max- max-pooling) between the activation layer and the final layer u like in eq. this gives additional freedom to construct the final invariant features beyond just average pooling.
23

---

Published in Transactions on Machine Learning Research (01/2025)
B
Mathematical Preliminaries
This section gathers the main tools we will use throughout the proofs.
First, we introduce the decoupling technique Foucart and Rauhut 20133). which will be used in the proof of the next lemma.
Theorem B.1. Let c= (c1....,cmm Cm) be a sequence of independent random variables with Be, = 0 for all E [m]. Let æjjk, j.k E [mi] be a double sequence of elements in finite-dimensional vector space V. If F: + R convex function, then:
m Σ
m Σ j.k=1
EF
SEF
(13)
Jakm1 jtk
where c' on independent copy of
The following lemuna can be found in Foucart and Rauhut (003)) namely inequality (8.22), within the proof
of Proposition 8.13. We re-state the lemma and the proof here, as it of independent interest.
Lemma B.2. For any positive semidefinite matrix B, for 83 B 2-4 < 1, and Rademacher vector e, we have
T B)
Ec (exp (Be' Bc)) S cxp ( 11-83 B 2-42
Proof. We start by using Theorem B.1
E exp (3c Be)) = E
exp B
B
Bjj + 3
>
EgceBB
j=1
jzk
sydulbae) )
< (exp (B)) E
exp
43 >
j,k
Then using the inequality Exxp( Em i== a1ε))
E Eexp( 8
Σm -i=1 a2/ we have:
Σ Big ())
exp
48
Σ
Bi
< E
exp 8,32 Σ
Next, see that:
Σ
Σ
Byb
= |B =
1/2 1/2
1/2
B
1/2
|| |B Be.
2-2
Therefore, for 83 [ 2-222 < 1, we get:
E (exp (BET Be)) S exp (3 (8Tr(B) (exp (882 B 211222 6 Be))
Bl1
S (3 ((exp (3E Be)))
8.8 Bl12-2
Rearranging the terms yields the final result.
24

---

Published in Transactions on Machine Learning Research (01/2025)
B.1 Rademacher Complexity Bounds
The generalization analysis of this paper is based on the Rademacher analysis. We summarize the main theorems here. The terms [(h) and L(h) denotes, respectively, the test and the training error, formally defined as follows:
[(h) = Empr, (fo)(x))) ((h) = 1 Σ to h(a.).
(14)
1=1
The empirical Rademacher complexity is defined as:
Rs( = E. sup 9Eg
(15)
Theorem B.3 (Theorem 26.5, Shalev-Shware and Ben-David 2014)). Let H be family of funclions, and let S be the training sequence of m samples drown from the distribution D Let & be real-valued loss function satisfying [ S c. Then, for E (0, 1), with probability at least 1 - we have, for all h E H,
2 llo((4/8)
((h) s ((h) 2Rs(f H) + dov
(16)
Using Theorem B.3
we can focus on finding upper bounds for the empirical Rademacher complexity of fo H. Below, we show how to remove the loss function {(.) and focus on H.
A function @ - IR called contraction if [@(x)) ((v) S | yl for all x, y E IR, or equivalently the function is 1-Lipschitz. The contraction lemma is standard result equation 4.20 of Ledoux and Talagrand (2011). We will use that for the Rademacher complexity analysis.
Lemma B.4. Let Φr : - R be contructions such that (0) O. TJG + R convez and incrensing function, then
m S EG
m
EG
sup
Gei(ti)
sup
Gti
(17)
Let's rewrite the Rademacher term, including the loss function explicitly:
1
Rs(E H.) = E. sup NEF m
Σ e,e o h(xx))
We assume I-Lipschitz loss function, for which we can use the contraction lemma, 4.20 in Ledoux and Talagrand (2011), to get:
Rs(e H. < Rs(H).
So finding an upper bound on Rs( is sufficient for the generalization error analysis.
B.2 Dudley's Inequality and Covering Number Bounds
Although, for most of the proofs, try to directly bound the Rademacher complexity, there is way of bounding it using the covering number of the underlying set. The covering number of set G is the minimum number of balls required to cover the set G with the centers within the set, the distances defined according lo a metric d, and the radius fixed of a given size e. is denoted by AN(G, e). The covering can be understood is a way approximating each point in g by a set of finite points of 9 with the fidclity c. The following result:
can be found in many references including Foucart and Rauhut (2013 Bartlett al. (2017); Mohri al. (2018).
25

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem B.5 (Dudley's Inequality). The Rademacher complexity be upper bounded using the covering number follows
B5.9
1
4 vm
sup DEg m
inf a>0
4a
Vlog (G du
(18)
where do(s,t) is metric defined on for any s,t as follows:
1/2
1
d(s,1)=
Σ
(s(x;)) 1(2x)))
(19)
m
i=1
and
E g )
Bs.g sup gEg
The idea to find a bound on the covering number and then Dudley's inequality to bound the Rademacher complexity.
C Proof of Main Theorems
C.1 Rademacher Complexity Bounds for Group Convolutional Networks
Consider the group convolutional network with co input channel, a intermediate channels, and last layer with pooling and aggregation. The input space is assumed to be x Remember that the network was given as follows:
E w(,)) @g a<k)
Nun (x) = uu Poo
= u Poo(Wa))
Ek=1 (( @G æ<k))
where P(.) is the pooling operation. We denote the first convolution layer with the circulant matrix Wa. To find bound on the Rademacher complexity, We start with the following inequality, which is shared across the proofs of some of the other theorems in the paper:
E
sup u,w
u Poo (W
Mi
E.
sup 2
Σ
Pooo
(20)
17
1=1
The above result follows from the Cauchy-Schwartz inequality and peels off the last aggregation layer. We continue the proofs from this step.
C.2 Proof for Positively Homogeneous Activation Functions with Average Pooling (Theorem C.1
Theorem C.1. Consider the hypothesis space H defined in eq. 4 If P(-) is the average pooling operation, a(-) is a L-Lipschitz positively homogeneous activation function, then with probability at least and for all h E H. we have:
L(h) < ((h) + Mi 41
log(4/0)
m
m
26

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. For imput E Rlo the action of the group G each channel is given by the permutation of the entries. Suppose that the G-permutations are given by IT,..... [[.. We have:
)
G
co
w
@G x.()))
E
sup
P (Wo)))
Ee
sup w
Σ Ei
1
ca
(o @ (k)))
w k=
Co
(1,2) I1 (1:)
Ee
sup
i=1
w A) (Tx)
o w (1,) 11.3s (13x,
m
S Be
sup
Σ 4
Σ k= (o (120
E w1,,s) 11,20 (1:
GG
m
Σ
sup
Ei
Ee Ek=1 w ((.. TTa,, (k)
where we used triangle inequalities for the first inequality. The second inequality follows from swapping the supremum and the sum. Consider arbitrary summand for given 1. We first use the moment inequality to get:
Cg kml
E
sup w
i=1
Σ co
w (c),)) k) (122(())
k=1
cD
w
m
S
E
sup
Σ 6s
(21)
i=1
a
00 Ek=
w kk)
(k))
We can continue the derivation as follows. First, define W(s) == (wg,)eefo)) which is the weights used for generating the channel j. Now, using the assumption of positively homogeneity, we have:
o Ei w (1, ((z,(k))
m
Co
Eg
sup
Σ
E2
E.
sup
EGO
Σ w (12
w (() (122((k))
k=
60
E.
sup
w ?
Σ co
|
w U.,y (az;(k) (k:
Since
|| < M2. we have
" 2| < M2.
27

---

Published in Transactions on Machine Learning Research (01/2025)
We similar trick to the paper Golowich et al. 2018 to focus only channel for the rest:
Ec
sup w
Σ
60
|w
w (1i))
(Tac,
j=1
1=1
k=
m
$ Ee
sup sup jE(a)
Σ i=1
6
Σ kmn
m
cD
2 21 (A:)
$ M
sup x
Σ
Go
2i (1)
||
Now, we can use the contraction lemma and get:
m
Ca w (is)
1)
m
[ )
E
sup 1
Σ
GGO
(1) (1)
Ee
sup
Σ E2
w
c0
Ex
sup
(K)
Σ e.l
S
E.
Σ
<mb?
(22)
where we used the fact that the permutation matrix II, is unitary. Putting all this together, we get:
Eie k=
I ((a,
G
by Mi M2
M
Ex
sup w
Σ
Vm
Vm
i=l
cg k= w win, (1)
1=1
which finalizes the desired results.
C.3 Max pooling Operation Covering Number Based Results
Single Channel Output. Before going into another result for max pooling, we focus on a simpler example. We assume ReLU activation throughout this subsection. First, consider the following network:
hw (x) = Poo Σ ((1)) @o x(k)
where P(-) is the max pooling operation. Just like above, we assume that the norm of the parameters is bounded by M2 while the input norm is bounded by bx. A special case this setup has been considered in Vardi al. (2022) in Theorem 7, where cp = 1. We recap their proof, providing a more refined final bound. The only difference is that, in our proof, use Dudley's inequality.
Theorem C.2 (Single Channel Max pooling). Consider the hypothesis space H of single channel group convolutional network with P(-) as maæ pooling, and a(.) as ReLU. With probabilily al least 1 and for all h H, have:
Mg vm
2 (og(44/))
(4/8)
E(h) S ((h) +
+ 2)m|G| + 1) log(m)) + 4
m
Proof. The proof consists of deriving the covering mumber NHH, d, u) and then using Dudley's incquality, We have included the essential components of such proofs in the section mathematical preliminaries.
28

---

Published in Transactions on Machine Learning Research (01/2025)
First, rewrite the convolution
((1 @g a=kk)
Σ w (1,A) (k
[w] (gg) gEG²
SEG
where w1 is the vectorized form of concatenated convolution vectors, and By is the vectorized form of concatenated [k)) Using this notation, we have:
d(hw: hw))
-11
1 Σ m 1=1
Poo (w xi.)) Di gEG - Poo (v x1o)) (vToro) gEG)
(2)
and using the Lipschitz continuity of max-pooling and ReLU, we get:
Pod (w (w"xx) gg) - Poo (v) gEG
I max gEG
(w - xz
This mcans that it suffices to get covering number for the lincar function (w T To Diglie[m] geG the extended dataset. We use the following lemma from Zhang 2002), which is stronger than a similar result using Maurey's empirical lemma Pisier
1980
1989).
Lemma C.3. If h((a) w/ with | < by and ||wlll S w for S p 0o and 1/p + 1/9 1, then for all 0
log (H, b0 u) s (36(p- 1)wbb./ /u)
+ 2)m 1).
where m is the number of samples.
This lemma bounds the -orm covering number, which an upper bound on the covering number W(H, d, u) used in Dudley's inequality.
In our case, the effective number of samples is m m|G], and therefore the covering number is bounded as:
log log,N(H, d, u) (36b, u)2 log() (2g2244b 2)mlGl + 1).
We just need to plug the above covering mumber into Dudley's incquality and use standard incqualitics:
Bs.
4
4
4a
VlogW(HH u) du < 4a
(36b,, (30,,M//)))/og((((H). 2)m + 1). du
vm Ja
Vm
4v2
< 4a +
(36b
Vm
by choosing = (2.M2/2mmm m, we get the following bound:
2b, M2
4
(366, M2) 1og(22/) 2)m[Gl 1) log(vm)
Vm
m
which yields the desired result.
Note that the bound is independent of the number of channels cp, but has logarithmic dependence on the group size, as well as other constant terms. In comparison with Vardi et al. (202)), we do not have the dependence on the spectral norm of the circulant matrix, although, as we indicated before, their proof works well the norm of parameters as well. In this sense, our result can be seen as the generalization of Vardi al. (2022) to the multi-channel input.
29

---

Published in Transactions on Machine Learning Research (01/2025)
Multi-Channe Output. Next, focus on the following setup with multi-channel convolution given by the matrix W:
Nu (x) - 2 (Wx)
We have the following theorems for this case.
Theorem C.4 (Multiple Channel Max pooling). Consider the hypothesis space H of mmlllpple channel group convolutional network with P(-) as max pooling, and (.) ReLU. With probability at least 1 and for all h E H. have:
((N) E(h)
ba Me
2 1og(2(166mm + 2)ml/G + 1) log(m)) + 4V
2 2log(4/8)
vm
m
Proof. We would need a covering number for hu, (X) == (hu w (z1)..... Ne, w (2m)) in norm We do this in two steps similar to the stratogy in Bartlett al. (2017). As the first step, we find ó1-covering un for the following set:
Hi o (W x):
|||||| S M2
where we used the notation WX X to denote the concatenation of all points in the training set, namely:
WX = (Poo Poo W))))
To simplify the notation, we assumne that that matrix operations are broadcasted through X if we have parallel compute over ss.
The second step consists of finding dz-covering for the set of u un for each us 's from the first covering. Using these two coverings, We have:
d (hu, (X). vi) wo (X)), ux) + d (u ux vi)
S M2d (P o a (WX), us) - d (u T us, vi) S Mdi + 62
(23)
where the norm d is defined in eq. 19 for any functions defined over the dataset (æI,.... .m). Besides, we assumed the points di and uy are chosen from the cover to satisfy the norm inequalities above. The final covering number is the product of the covering numbers from cach step with the covering radius M81 + 82.
We start with the second step, namely to cover the following set for any us in the first cover:
H2.4 == {u un || M1).
The elements of the first cover, ug are themselves instances of the first layer of the network. Therefore, we can bound the second covering number for all le as follows:
d(H2,,, 62) supu Poo(WXX ||u||| < M2),d, d, 62).
w
This is an instance of covering linear functions. We will use the following result from Zhang 2002), which leverages Maurey's empirical lemma.
Lemma C.5. If h(z) = w" with ||01|, S be and ||00|l, S w, then
log (H,, d, u) < (2wbs/vv /u) log(2m + 1).
where m is the number of samples.
Since the norm of u is bounded by Mi, we only need to bound the norm of ug. First, note that | (WX] = Em Pod "= For each element of the sum, get the following upper
30

---

Published in Transactions on Machine Learning Research (01/2025)
bound:
2
|Po (W x;)) x1 Σ Poo
(1,N) @G ax(k)
max
(1,A) @G ax():)
1=1
2
(i,)) @G ax())))
max
( ||~(())]]]
Σ (+)))
|
b MP
where the first inequality follows from the property of ReLU, and the thrid inequality follows from Young's convolutional inequality. Using this inequality, we can use Lemma C.5 to get the following:
log NogW(H2,,x do 62) < (2b M1 M2 / m/ /2) (2m + 1).
(24)
Now can move to the covering number for H₂ {P (WX) ||l|| s M1). Given that the ReLU function is 1-Tipschitz, it suffices to find covering for P(W X), and note that the covering norm is mixed norm, namely:
1/2
U( = m71
P(Wx:)) - U.1?
2
1/2
max Σ w(,i @ (())
U
m
j=1
To find the covering number, we use the following set inequalities:
2 Un.s
1/2
U)
max mE(m) j=1
max
((A)) @ (1(4)
2
1/2
|
w(i))
&G (k((k))
Us |eoc
max
max
Suppose that we find cover Un, that satisfies the following inequality
max ke (m) [E(L)
max
co
wGk)
@ ai(kk)
U.s
81 Mi
(25)
wGal
Then, it is easy to see that since E ( 2 < M1, then
2)
1/2
cD Σ
)
((P(WX))U)=
( BG ax, (A:)
-l Uiss
8
k=1
31

---

Published in Transactions on Machine Learning Research (01/2025)
To find such covering, first find cover for this set:
{
{max max Σ
Go
(w) @ 2z (k)
||00||| S 1
iE(m)
Note that this is a special case of the covering number of the single-channel networks, which we had computed above. This set is the super-set of functions represented by each channel when the weights are normalized to have unit norm We find 01 independent covers, one for cach channel, and this will give us the desired covering in eq- 25 We use the covering number for the single channel case using M2 = 1 and u = 51/M2
(which basically does not change the bound on the covering number) to get the ultimate covering mumber for this layer given by:
log (H1, S (H, - ci (366__M2//11) log(2(4b, M// + 2)m[G) + 1).
(26)
The final covering number is the product of the new covering number, and what obtained for the last layer. Therefore, using the inequality eq. 23 and the covering numbers eq. 24 and eq. 26 the final covering number can be bounded as:
& log.N (HH d, 6) S log max (N,,, d, 4ogg
M,g( 2)m|Gl +
2c1 (7 M1 M2 log( M2/6 2)mlGG + 1).
We can plug into Dudley's inequality, which gives us the following bound:
4/2
4a +
log N (H,,d d, du
vm
4V2
< 4a +
Mi Ma 2)m/G] +
/m
We can choose b..M, M2 / / mm, and we get the following bound:
M, M₂
2/2 (cT(22b, log(2(166mm) Mo0gT22,,MMM))0gg(((22 2)m/Gl + 1) log(m)
mm
vm
The result. follows from a standard inequality.
Apart from constant terms and other logarithmic terms, this new theorem has an extra dependence on vei, which is the dimension the output channels. For the rest, we recover the term M2 M2//m which is what we expected. Unfortunately, for max-pooling, the dependence on /ci seems to the artifact of using the covering number argument. As we will see in the next section, the direct analysis of Rademacher complexity shows that the dependence G₁ be completely removed with the price of additional dependence on the group size and input dataset.
Remark C.6. The covering argument above strictly better than the method used in Lemman 3.2 of Bartlett et al. 2017 for covering matrix products. If we use this lemma, we get a covering number of the form:
(baMalGi) 2 2
log(N d) sei
log(2(G(eerco).
As one can soe, we have now further dimension dependence in the bound, basically on the number of input channels cu and [G]. In the original paper, they could use mixed norms |1=Ily.. get rid of some of the dimension dependencies, which cannot do in setting.
32

---

Published in Transactions on Machine Learning Research (01/2025)
C.4 Homogeneous non-decreasing activation with max pooling
The following result provides a similar upper bound for max-pooling, A bit of notation: fix the training data matrix X. Denote the permutation action of the group element / e G' by 14, The vector I = (I..... (m) e [[[]]" determines the group permutation index individually applied to each training data points. For each we get the group-augmented version of the dataset denoted as X₁ = ( IT,,, Fm)
Theorem C.7. Consider the hypothesis space H defined in eq. 4 Suppose that P(.) is the maz pooling operation, and o()) is a 1-Lipschilz and non-decreusing posilively homogeneous activation function. Fix the training data matriz X. Then with probability at least 1- and for all h E H. we have:
Mj M29
2 2log(4/5)
[(h) S L(h)+ +2
4V
vm
with g(X) defined as:
g(X) = (8lg + ba +
/ M2 62
where M = maxi
X7 X1
2- for the group-augmented training data matrix Xt-
The proof for max pooling leverages new techniques and is presented in Appendix C.4 The generalization bound in the above theorem is completely dimension-free (apart from logarithmic dependence on the group size in gX)).. The norm dependency is also quite minimal. The bound merely depends the Euclidean norm of parameters per layer. Note that the norm is computed for the convolutional kernel w, which is tighter than both spectral and Frobenius norm of the respective matrix W. Finally, there is no dependency on the dimension or the number of input and output channels (co, c1). The term M is new compared to other results in the literature. This term essentially captures the covariance of the data in the quotient feature space. The term M is defined in terms of the spectral norm, which is lower-bounee by the norm of column vectors, namely by. See Appendix C.4 for more discussions 2,
We start from eq. 20 where the first layer is peeled off. One of the key ideas behind the proof is that if (.) is positively homogeneous and non-decreasing, the activation of)) and the max operation can swap their place. We have:
max Ø (E k= (1.)) @G (x))
1)
E2
sup uP
P o o W Wz:))
E. sup u
Σe
max a (E co k=1 ((r @ n. (k))
[max k= ((,8) @G 2z (A:)
Eg
sup
w
00 max
k= ( @ x, (k))
Then, similar to the previous proof, we use the following moment inequality:
a (max
Σ c (1,8) @G x, (A:))
Ee
sup
E
i=1
a (max Enu w (c),k) @ xx))))
a (max Eee k- w(1.) @G (k)) 122
E
sup ap
i=
mmax Eie kz (G k) @o xx(k))
We then use the pfeling-off technique similar to the proof above for the term inside the square root:
33

---

Published in Transactions on Machine Learning Research (01/2025)
(max Σ ((L)) @G Dz [x)k) ()2
Ec
sup a0
Σ
i=
(max E (e) @0 ai(k))
a (maxielial Ei= w ((.)) (aax
m
Ex
sup
maxielIGi| Ei=r (c (222(()))
G1
m
Ex
sup
Σ
6j0
max |E[|G)
(i)))) (1))
M
sup w
6
max [E||G]
T (
(k)
To continue, we define E [[G]]" as the vector of (l,...., (m) with 4 E [[]]] contraction inequality and some other standard techniques to get the following:
Now, we can first use the
Ec
sup [oll
Σ EGO
max [E|[G]
w
Tha (k)
wi
$1
Ee
sup
C.
w (R) [1)x (k)
(27)
s0:||10|| 11
IE||G]]
< E.
sup
max
Σ (1k) IT, a1 (k)
w:||w|||
A=
Eg
sup
max
(K) Σ x.Il(x((Kk)
w:||w/||
< Ex
max
Σ e edll,
where abuse the notation II, 25 to denote the channel-wise application of the permutation æ; (assuming ar is shaped |G| eg). We the same term T1,2 to denote its vectorized version to avoid the notation overhead.
Now, see that for B > 0,
m
m
3E,
max
Σ
c 11, æ;
= E.
log exp max 3
Σ
c M1 a
< log Ee
maxexp 8
Σ E1 33
< log E.
Σ exp
Σ
E M, 27;
34

---

Published in Transactions on Machine Learning Research (01/2025)
We now use the Lemma B.2 Note that, in our case, we have:
11 2z
||xe|| = c =c x7 Xic,
where (41, (cI,..,,cm. == and
X
II Tm). We now choose B X X₁ in Lemma (II, 21
B.2 to get:
m
(X Xi)
log Ee Σ Expp 3
Σ
G 11, 11 Zi
S log Σ exp
1- 8, Xi
Xt
2-2
(T X X)
log
Σ exp
8/3 X1 Xt
2-2
Bmb
S log
Σ exp
8,3
Bmmb
S log
|G| exp
1-8,Myyx*
where M = maxt
Xi X1l12-22
Note that we have assumed 83M S We then have:
m
m log((G))
mb
Eg
max
Σ
e e,ll 2i
<
8
8, M
Note that
+ b
max
1 cB = ac + b abc,
8 B
obtained for 3 1/ (c+ vbe/a) We need to assume that 83M S which means:
8M
& (SMER + (8 62/ |og
This is always true, so choosing B accordingly, we have:
m
Ex
max
Σ
8m log(IG))MM mb? + m (88800((G)))MMux33
which gives us the total bound:
Mi Ma Gl) Ma + 12 + (llg((|)) M
m
Remark C.8. Ignoring the term M the bound is dimension-frec. The term M depends on the data matrix's spectral norm with normalized columns. Remember that:
M max | X1 X1
The spectral norm of X X is the spectral norm of the sample covariance matrix of the data. Consider an extreme case i.id data samples with the diagonal covariance matrix; the spectral norm X X will be (m)) as m - co. The situation remains the same for an arbitrary covariance matrix. other words, this bound is loose for large samples. However, in small samples, the spectral norm can be smaller (for example, assume X is approximately orthogonal matrix).
35

---

Published in Transactions on Machine Learning Research (01/2025)
It important to note that the term M2 appears for bounding E. (max |Σ &,11,=11% which itself
appeared in the step eq. 27 We can consider max-pooling as a Lipschitz pooling operation and techniques similar to Vardi et al. (022) Graf et al. 2022 to bound the term. However, this would incur an additional logarithmic dependence on the input dimension and m, but it will be tighter m + co. Ideally, the ultimate generalization bound should be the minimum of these two cases.
C.5
General Pooling
In this section, we consider the case of general pooling. The proof steps are similar to the classical average pooling case, so we present it more compactly. We first peel off the last layer and use the moment inequality:
1 T a (Etn
@a 2x(())
m
))
G
k=l
((LA)
Ex
sup
Σ e o
W a2))
E.
sup
Σ iml
w () @G x.((k)) (2
[c]
((,b) @ xb((k)
G
E2
sup
Σ c
i=1
1 a
1
(E
I w .) @c x.)k))
The next step to use the peeling argument and contraction inequality step by step:
( |
1o
(E k w(L
@ 2k))
E
sup
1
(>e=
co k==
(( B0 ai(k)))
1 |G
Ee
sup
TJo
(i,)) @o (i(k)
10
j=1
im
Ee
| sup
2
1
TTo
(Gaa) @G (i((k)
G
w
1=1
1=1
m
< .M3E E,
sup
1
(K)
@G xi (k)
GG]
m
80
< M2 E.
sup
E
(() &G (k)))
|00
k=1
s M2
1
|G|
Ec
sup
Σ
m
Go
Σ
6o
(wy 1ix (k)
G
||
And then we can re-use what we proved eq.
22
to get:
m
eo Σ
E
sup
E
w
1) [1xx(()) (k)
||o|||
2) (k)
co
))
sup
61
w (k)
11 (k))
ml?
[
w
Putting all of this together, get the final theorem.
36

---

Published in Transactions on Machine Learning Research (01/2025)
C.6 Proof for Multi-Layer Group Convolutional Networks
In this section, prove Theorem 1.3.
We start again by simply peeling off the last layer:
Eg
sup (M(((),,E(()))
1 m ==1
e T Poo (Wr.z(-11)
M1 Er sup (wet))
Σ e P PoPooWWane
(Wo
(aa (28)
m
where, for brevity, we use ((L-1) to denote the output of the hidden layer --1 1. We can expand the average pooling operation and use the positive homogeneity property of ReLU function to
Cl-l (L).T a
k=l (1,6) 11 (1-2) (1))
GG
Eg
sup [w]])
Σ 1=1
CePoo (Wx
B
sup (w()),t((])
Σ i=1
ci
GG|
a E w (cr,k) 1 (1-1)) (k))
and then, we focus on single term and use simple Jensen to get:
DE w
(L)TT (1,K) 11 11 (1-11) (16)
Ex
sup (E(])
c k=
w (L),
II 11-1) (8:)
(oz,R)
(1,k) ng (Le (1-1) (1t)
(L).T
k=1
w
m
Ee
sup (II(),
Σe
ch- (L), T
(ct ngz! (1- (1:)
and we can continue with similar approach simplify this further:
pe--1 (L),
(1 (1-1) (k)) (1,b) 11
Eg
sup (w(,,ELL]
Σe Ei
> k=1
w T
11, I1
x
(L- (1- (16)
()),))
Ee
sup
un G++)
2
60
1
w
(L). T (j.k)
II ng (L- 21 (K:)
/=1
m Σ
< Mf
sup 13:
w (L)) T 11 2
(k)
111 11
(1o(0),E(L_-1)
A=1
m
< M.
sup
Σ 6
(mo(),E((L-1])
1=1
37

---

Published in Transactions on Machine Learning Research (01/2025)
where Hy is unitary matrix and was removed. Now, have removed the last layer from the bound, and we can focus on the rest of layers.
m
E.
sup (E(.)))
Σ
4
2
(1)
i=1
Σ I
w
(1.K)
(1-1).T
x 22
Eg
sup (10-))
Σ Ei
i=1
Σ k=
w (I-1):T
(cz-
@ a
(1-2) (1))))(k)) (1:)
GG| CL-1
11-11112 2
Ee
sup
1 (i+)
Σ Eo
(1-1-1) (f:)
w (1-11)
(j:b)
11
(1 2) (K)
(wo()),E(L-1]
11} g=1
R=
|G|
CL-1
10 ( 1|2
m Σ
Cx-2
w (1-11),
T 1ga (1- (1s)
Eec
sup
co
w (L-1) (1:))
(j.b)
g
[E([T-1]]
j=1
i=1
R=1
m
S SIG|ME-
Σ
Ei x (2)
sup (w0)) 11)
Note that the last step involves the very same peeling argument for each term in the sum, and we removed it. Doing this iteratively, we can peel off all the layers, and get the final result. It is worth noting that the authors Golowich et al. (2018) provide a way of converting exponential depth dependence to polynomial dependence. Using this technique we can change the depth dependence from |G) to (L - 1) log G| for I. >>> See Section 3 of Golowich et al. (2018) for more discussions.
C.6.1 A generalization bound for gradual pooling
In this part, we consider a version of the multi-layer network with gradual pooling, We consider the following model:
( ([(L)) (a) == T. Pt a
... (ooo(W())...))
(29)
where the pooling operation changes the group size of cach layer gradually to 1 as follows:
G P.(G:=Co/&.), G. P.(G)=G./Ga), G2 - . ....GGG- Pu(Gz=Ge-1/Gu GL= 11
In other words, the pooling layer at layer I pools from the cosets G, == / for example by averaging out the elements of each left cosets. It can be seen as moving the operation from the group G. G.. This also means that: G Gol |G1 |Ga |2 = |G1 x 1Gu)
Define the corresponding hypothesis space of functions with gradual pooling as follows:
H.L- = (hu, ||x||| S M1. |wm||| S M411 E [4]]
(30)
We have the following theorem for this network.
Theorem C.9. Consider the hypothesis space in eq. 30 consisting of functions defined in eq.
29
With
probability at least 1 - 5 and for all h E ((--),.).), we have:
1.
b M, M2
M
2 llo(44/))
((h) $ 2(h) +2
I1 1=1
Gil
+ 4v
vm
m
38

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. For the rest of the proof, for simplicity, we assume that the elements of G, = Gi-1/Gi is represented by a member in GL-1 such that any element. in G can be written uniquely as 9'-9 where o' Gi,g E Gt.
The key for the proof is the intuitive observation that at each layer, we could use the group size utilized at that layer, more formally:
Eg
sup (w(t) _E|
Σ
1 00
(1.k)
(1-1)
2
(k))
Gz-1
Ee
(wo(),tE 1]}
sup
Σ g'EGi.-1
Σ
G-
1
Σ
(1,k)
(1-1),T
IT xx
8'3
(1-2) () (R))
g=l
k=
Gi-11
1 Ex
Σ
(L-1),
11 11
(1- (1- (k))
G1.1
(wo(t),E((--I)
sup
11}
610
(1.b)
xi
o d'EGi-1 gmd I
i=1
G1-1
Ex
(1o(1),EELL-
sup
Σ
Σ
(1,R)
(1-1);T
IT 1 (L-2) (k)
x
gEGi--
i=l
GD-2
GL-1 1
(1-13)
(1,:)
Ee
sup
Σ
m
G
x
(b-2)
(w.(0,,E((--2])
i=1
S G
w
[1,s]
(1-1)
EE
sup [w(O (w.(LEELL--)
Σe, Ei
(x!
(0((-2)
Using the above argument, can revisit the proof above and see that:
m
Ec
sup (1o()),E((L
Σ
(1-
1]}
PL-100 Eel-3 w x (1(1-22) (1)
(1-1),T
(1.A)
m
Ee
sup
Σ 6j
(wol) (E((0,
PL-100 10
Ech-
w (ec 1nk)
(1-1),T
x
(I (L-2) (1:)
Σ
(L-2)
sup (wil)) (E 2
i=1
We omitted many steps in the proof as they are exactly similar to the proof above.
Remark C.10. We would like to highlight that the gradual pooling breaks the equivariance with respect to the original G, and it is not a common practice in geometric deep learning to do it, in contrast with typical convolutional neural networks.
D General Equivariant Networks
The general equivariant networks are defined in Fourier space as follows:
Ha, = { Q2a(Q w
Here, we assumed that the input is already represented in the Fourier space é. The input and hidden layer representations are the direct sums of the group irreps s each, respectively, with the multiplicity mo
39

---

Published in Transactions on Machine Learning Research (01/2025)
and m1.e. Since we working with the point-wise non-linearity in the spatial domain, two unitary transformations Qi and Q2 are applied as Fourier transforms from the irrep space to the spatial domain. Finally, to get an invariant function, the vector à only mixes the frequencies of the trivial representation Vo, and it zero otherwisc. To use an analogy with group convolutional networks, Q1 and Q2 are the Fourier matrices, and á a combination of the pooling, which projects into the trivial representation of the group, and the last aggregation step. The hypothesis space represented as
Ma.s ma.e W ((0.6.)000003)
H =
át Q2a
Q
t=1
j=1
We start the proof as follows:
M1
Σ Go (U W vi:
Ec sup
(2 (a)
E
sup
ú.
1=1
w
!))
2)
1/2
M1
Ec
sup
Σ
6 Q1 W
W
:=1
From this step, we can re-use the pooling operation:
wai)
Eg
sup
Σ Go
(Q (Q
W
W
E.
sup
Σ
Σ Eio Ii W wi:)
W
E.
sup
Σ
91 w12
2
Σ
qi Wa:
T
| w
W
1=1
< E.
sup
Σ
ai W
sup W.j
Σ 6:5
9 We:
W
1=1
1 vv
1)
2)
m
S ME
sup W
Σ 6:
(1 w
Th. W.:
Note that we used the following:
w|( 1| =
[ 1/ |w|²= < M13
-|
40

---

Published in Transactions on Machine Learning Research (01/2025)
Then, using the contraction lemma, we obtain:
1)
Eg
sup W
Σ
60
21.3
T
W d;;
i=1
92.
W
m
sup w
Σ
61
11 W
9i W
i=1
m
E
sup
Σ Gi W
G
9 W
W.j
S E.
C
S mb
E Lower Bound on Rademacher Complexity Proof of Theorem 4.4
We now provide a lower bound on the Rademacher complexity for average pooling and ReLU activation function. The authors in Bartlett et al. (2017) and Golowich et al.] (2018) provide lower bounds on the Rademacher complexity. Their results, however, do not apply for group equivariant architectures given the underlying structure of weight kernels. Similar to Golowich et al. 2018)) our result holds for a class of data distributions.
As the starting point, we again peel off of the last layer:
E sup Σ ==1
u Poo (Wa)
Mi m
E.
sup t
Σ & P (Wai) Pooo i=1
(31)
8.30
The next step is to find a lower bound on the right hand side. For that, we consider only weight kernels that are non-zero the first channel and zcro otherwise. Plugging in the average pooling, this mcans:
G T (E ((1.) @G xx()))
m
)
m Σ 1=1
Ec sup Σ
(Wo)))))) &ePoo
2 E.
sup wEW1
E
(32)
where Wi is the set of weight kernels with zero channels everywhere except the first channel. This can be further simplified to:
1 k= ((1) @ xx(())
E
sup Wo Wi
Σ
w T
T1a (A:)
(1.A)
m
0
E.
sup
WEW
G
:
0
G
Cg
(1.A) T1 (A:) )
E.
sup
WEW;
41

---

Published in Transactions on Machine Learning Research (01/2025)
We assume data distributions of generality assume that arkk's s are supported over the positive orthant, which means that 1 ==(k) ||=((A)]]
such that each channel x z=k) is supported in single orthant. Without loss
We also assume that the data points have maximum norm || = B. Now consider subset W of Wi such that ((,))) 1 where ((1,)) is positive scalar value. With all these assumptions, we get:
G
)
IGI
(1,2) 11 (16) ))
E2
sup
4
0
w 1)) a (k)
2 Ee
sup wEW;
G
G
wEW
w(1A) mice(()) )
m
C9
Ee
sup
0
WEW
m
ca
E.
sup
>
w()
WEWT
w(1,)) 21(1)) ))
Ee
sup wEW]
c
where the last step follows from the positiveness of ((11) 's and the assumption on the data distribution. We can now simplify the last bound further to get:
m Σ i=1
Σ w( 1 22((6) )1
Σ G xx)()))))))) )
m
Ee
sup WE
C
E.
sup WEW!
Σ w(1
W!
k=
1 1 (T))(1)
M2E,
ΣS c
1 (cu))
Using Khintchine's inequality, we can conclude that there is constant >>> such that
T (1)
1 x; (1)
E
Σ i=1
4
:
x
(co)
i=1
xz (co)
m
22 (x))2
2c, (k)
B Bym
For the last steps, we have used the assumptions the data distribution. This yields the intended lower bound.
Remark E. The lower bounds on the sample complexity are commonly obtained via fat-shattering dimension as in Vardi et al. 2022). The construction of input-label samples shattered by non-equivariant networks would not extend to equivariant networks (ENs), as the ENs can only shatter data points that satisfy the exact symmetry. There are works on VC dimension of ENs, however they are not dimension-free and do not include norm bounds similar to ours.
42

---

Published in Transactions on Machine Learning Research (01/2025)
F Frequency Domain Analysis
Let's consider the representation in the frequency domain. The Fourier transform is given by a unitary matrix F. For simplicity, here we assume the simplest setting of commulative compoct group G, for which have:
F(w @a x) diag(w))
where á = Fæ, and diag(t)) arises from the Fourier based decomposition of the circulant matrix W. Each frequency component in ub an irreducible representation the group G denoted by sb. Commutativity implies that each irrep has nultiplicity equal to 1 in the Fourier transform. Therefore, using the direct sum notation, we have:
diag( ())
(33)
See the Suppiementary Matorials A for more details. Note that the point-wisc non-lincarity should be applicd in the spatial domain, so we need an inverse Fourier transform before activalion. The network represent a aion in the Fourier space is given by:
F" i=
+
(()))) 2x(i))
(x) u Poo
(34)
F+ Di=l
+
v (os (1)) æx(i)
where F* denotes the conjugate transpose the unitary matrix F. Note that we have not touched the last layers. The last layer merely focuses on getting an invariant representation.
We show that conducting the Rademacher analysis in the frequency domain brings additional gain. The situation may be different if the input is bandlimited. We summarize this result in the following proposition.
Proposition F.1. For the hypothesis space H defined in eq. 4 the average pooling operation, o()) as a I-Lipschitz positively homogeneous activation function, the generalization error bounded as O M, /m
Proof. Consider the network represented in the frequency domain as follows:
Σ> co F
+
((119) ax(i))
i=
ha (z) = u Poo
(35)
F
E
(C afii)
A lew clarifications before continuing further. Consider the circular convolution @5 Note that the decomposition (+ ((())) is obtained by using the Fourier docomposition of the equivalent circulant matrix:
Fr
+ (v6)
F= W,
and therefore, when using Parseval's relation, should be careful to include the group size as follows:
Σ
- W| p
|G| ||
Now, let's continue the proof. For average pooling, we can start by peeling off the last linear layers and average pooling and continue from there, namely from eq. 21 Note that I'th entry be computed using
43

---

Published in Transactions on Machine Learning Research (01/2025)
inner product with the I'th row of F", represented by fi. We have:
Si Σ k=
+ v (1 (t)) 2;(()))
m
E
sup
Σ
w
(fi Σ k=1
+ (1)))))(1) xz 22((6)))
x.(H)) )
Eg
sup
Σ Ed7
fi
Σ
A
(+))
w
j=1
1=1
k=1
Ee
sup
Σ
6o
|
fi
A (.)))))
xx(k))
A=
where we used the positively homogeneity property of the activation function, and we defined:
||ا
(1))
v.ke(co]
We can use Parseval's theorem, and based on the discussion above, we know that:
Σ
|G|
Σ
||w s MG
jElo.]
sEle
And then, we can continue similarly to the proof of average pooling:
m
co
Ee
sup
||
ا
2
Σ
6,
Si
Σ
-
((a ax((k)
1
<
G
sup rb: Kb &
c
fü Σ Jmm
+
ax((1))
i=1
From which continue using contraction incquality:
2)
m
8
E2
sup 10: 1i
Σ
fi
A s
(e (w)
a.(k))
A=1
co
< Ex
sup
Σ fi
fi
A
vireo (16)
an((k))
k=1
< Ex
sup
fi k=1
((0)
Σ escos(
1
m
sup ان
fi
+ 1
Eec
Σ c
kE(cal
F
sup
fi +
(()))())
mb3
kE(co]
44

---

Published in Transactions on Machine Learning Research (01/2025)
To simplify the norm the feft-hand side, it is important to note that each entry of f? has the modulus 1/v //v/G, which means that
1
sup 1sl
fi
- (15)
G
kE(co)
F
The term G/|G| cancels the term [G] in the previous inequality and yields the bound. The result shows that there is no gain in the frequency domain analysis.
G Proofs for Weight Sharing Consider the network:
Ees Lk=1 ((,)) (k) x(c)
h nu (x) = u Pood
Ei
EEke w (( (k) Bx) x(c)
For the pooling operation P(-,, we consider the average pooling operation. The Rademacher complexity analysis starts similarly to the proof of group convolution networks. This means that we can peel off the first layer and consider single term in the average pooling operation, namely:
Σ
Σ w (1.e)
Gl k=
(k) x.((c)
Eg
sup W
Poo
E ==
Σ
G| k=
W .0) (k) az(())
|G|
20=1
k=
w (1,c) (c)())
E,
sup
40
G
m
1=1
fg
w (c) (k:) xx(cc)
c=
k=
E
k=
(1.e)
w
(k)b (c((c)
Ex
sup w
Σ
Go
G
i=1
w ( (1) x.(c)
kk
where by, is the l'th row of By. From here, we can continue similarly. First, we use the following moment inequality:
wi (1.) (k)) xx(())
R=
m
Eg
sup
Σ
G0 c=
w Wey (k)bb xi(())
k=
|G|
w W(1.o (A)b),1)) xx((c)
E,
sup 1
Σ
E
Go
|G| k=l
(ct .)) (k)) ai(())
2
m
oo
[
E
sup
Σ
w W(i (1)) x,(c)
1=1
i=1
45

---

Published in Transactions on Machine Learning Research (01/2025)
For the rest, denote (by abuse of notation, drop the index I when it is evident in context):
G
|
llB
||w/|| B ==
max rE[|G]]
Σ
(b)bk,
cEfcal F
sela
Note that:
G (.o)
|G|
w
(b)
S max IE[|G||
w ()) (k)bk,
S aM).
cElcal-Eleii
We can continue the proof as follows:
c1
m
Co
E
sup
w (.0) 6.0) (k)b
xi(c)
<
Ee
supp
2
Σ cạO
|
w (i,) (k)b)
2i(e))
B c=1
G
<
sup E.
Σ 60
|w
(i.c) (k)
x2(c))
w
1=1
B
c=1
1=1
< aM....) E
sup
Σ
Tw
w
Wi (1:)bk
xz(c)
i=1
m
S (M.
sup
Σ
Σ
(k)
ai(c)
where the supremum is taked over all vectors tō satisfying:
Σ
( (k)b
1.
cE(col
We can use the contraction inequality and the
inequality to obtain the following:
Ec
sup s
Σ
Go
i (1)) 2:((c)
i=1
m
co
sup 1
w (k)b
ax(c))
GG|
Ee
sup
m (1))
Erans (c)
S
sup
w(0) (k)b
Ee
Σ
c
I mb? x.
k=l
cE(co]
i=1
46

---

Published in Transactions on Machine Learning Research (01/2025)
H Proofs for Local Filters Proposition 7.1
Consider the network defined as:
Ek=1 W ((I.)))(((((i)))
LEi|G1
w (x) = u Poo
u u Poo()))))
-k=1 (())))))((((()) rE(|On/
where similar to Vardi et al. 2022)) W is the matrix conforming the patches & and the weights. The first steps for average pooling are similar to what we have done in Section C.2 The only difference is that (aa(k) is replaced with (k)))))) We will not repeat the arguments and condense them in the following steps:
Mi
Ee sup u.w
e,u Poo (Wa))
<
Ee
sup w
e P Poo
Σ k=
(1
G
M1
Ee
sup
Σ ci
w
i=1
Σ
co
k=
w
And, can repeat the peeling arguments to get:
Σ k=
w
(1
Eg
sup
S M2
Ee
sup ا S
Σ
(k)
i=1
a
w
(o
(zx
The only change in the proof is about the way we simplify the term in the square root:
2
Ga
Eg
sup W
Σ E,o
Σ
E.
sup W:
w
(1)0)((
T
1=1
k=1
E
sup
Wi (K)
Σ
(x)
w: tt0 11
k=
Σ (101((2))) 11
< E
Σ (x:))
(36)
Now we use Jensen inequality to get the proof:
|G]
1 Σ E T Poo
M1
Ex sup u,w
(b)()))) 12
G
1=1
M1
m
(2: (x
m
M M1
m0 |G]
M, Mybb
Ox G
m
vm
Uncertainty Principle for Local Filters Proposition 7.2
We start by stating the uncertainty principle for finite Abelian groups
47

---

Published in Transactions on Machine Learning Research (01/2025)
Reference
Bound
Equivariance (Theorem 4.1
b A22
m by My M
Weight sharing (Proposition 6.1
Vm
Locality (Proposition 7.1
On by Mr M2
Non-Equivariant Networks Golowich et al. (2018)
b= || Will IE
Weight sharing, orthogonal bu., l E
G
b b,M M2
vm M1 M2/ VmB
R-sparse filters
Proposition
7.2
Linear convolution Vardi et al.
(002)
VO
by 2
CNN with Pooling
Vardi et al.
(022)
bx ||l lla log my
Vm
Mg log( (og((G//max((ene) (eg. )) W ll
Graf et al. (2022)
mm
The table summarizes the main results of the paper and compares with the selected prior works. The top three rows are the main results of the paper expressed in their full generality (Reminder: M2 maxtellon
Table 2:
(E (k)bb) cE(cu).EEfeil]
). Next three rows summarize the result for the case where the
network not equivariant, the optimal weight sharing and the band-limited filters. The bound from the most relevant results also summarized in the last rows of the table. The explicit dimension dependency of these bounds are highlighted with different color.
Theorem 1.1. Let G be finite Abelian group. Suppose the function f G C is non-zero, and f is its Fourier transform. We have
(ssp(()).ssupp(())
(upp(() 2 |G].
If the filters have B non-zero entries in the frequency domain, then the uncertainty principle implies that the filter in the spatial domain has at least /GI/B non-zero entries. In other words, the smallest filter size will have |GI/B B non-zero elements. Therefore, the smallest possible upper bound we can obtain using our approach will use O+- = |G//B. Plugging this in Proposition 7.1 yields the proposition.
J Comparison with other existing bounds
The following works do not consider the generalization error for equivariant networks. However, the convolutional networks, which are studied in their work, are closely related to our results. We have also summarized our results and their comparison in Table 2
We focus on equivariant networks and upper bounds on the sample complexity. The networks considered in this work are slightly more general with per-channel linear and non-linear pooling operations. They also provide a bound in Theorem of their paper for pooling operations p | - that are 1-Lipschitz with respect to the loo norm. This class includes average and max pooling operations. Their bound has logarithmic dimension dependence, the artifact of using the covering number- based arguments (see below for more discussions). The bound is also dependent clear if the dependence on the spectral norm can be removed in their proof. For local filters, they provide a dimensionnffee bound that also depends on the spectral norm of W. However, this time, the dependence on the spectral norm can be substituted with the norm of the weight vector, as it evident from their proof. general, all our bounds depend only on the norms of the weight vector, which tighter than using Frobenius or spectral norm of W. The authors in Vardi al. (2022) provide lower bounds on the sample complexity, which we relegate to future works.
Comparison with Vardi et al. (0022). Our work is closely related to Vardi et al. 2022
the spectral norm of the matrix W instead of the norm of the weight It is not
48

---

Published in Transactions on Machine Learning Research (01/2025)
Comparison with Graf et al. (2022). The paper of Graf et al. (2022) relics mainly Maurey's empirical lemma and covers number of arguments. Rademacher complexity bounds either work directly on bounding the Rademacher sum through set of inequalities or utilize chaining arguments and Dudley's integral incquality. Dudley's integral requires an estimate of the covering number. The main techniques of finding the covering number, like volumetrie, Sudakov, and Maurey's 's lemma techniques, manifest different. dimension dependencies, with the latter usually providing the mildest dependence. Completely dimension-free bounds are obtained mainly via the direct analysis of the Rademacher sum. Therefore, the bounds in Grai et al. 2022) are mixture of dimension-dependeer and norm-dependent terms. Their bounds are, however, quite general and consider different activation functions and residual connections.
To investigate their bound further, let's consider their setup, locusing on what matters for the current paper. They consider a network with L residual blocks, where the residual block has Lg layers. That is:
f == o f o ......... 00 о fi with f((x) = ge(x) + OiL, haz, 0..000 o h,1 (z).
The activation functions d; and oij have respectively the Lipschitz constants of p; and Pij- The function gi(:) represents the residual connection with go - O. The map hy represents the convolutional operation with the Kernel Kg. The Lipschitz constant. of the layer given by 8ij, which corresponds the spectral norm of the matrix that conforms with the layer (similar to the spectral norm of W). The f2,1 norm of the kernels Ki is bounded by bi (this can be initialization dependent independent). The norm of K E Rexeexdis defined as
| | = =Σ |I
Define s; Lip(s.) +1 PijSij. Denote the total number of layers by L, Wij is the number of weights in the j-th layer in the i-th residual block. Set W max Wej. And Cg represents the dependence on the weight and data norms:
C₁
||| mm
2
II
sipt
I SiPPik by
83
Stg
Define = = 20t// where y is the margin. The authors have two bounds where the dependence on W appears logarithmically or directly. We focus on the former. The equation (16) gives the gencralization crror as
(V
log(2W) En, I'O2
o
First, have W =|G| max(co, e1). Secondly, for the first layer, we have:
On & by (811812) 811812 dn
bab11812 S M2 |1ll2211
811812
with
2.1
1=1
Finally, for the last layer, we get:
$11812 b1
C2 < by (811812)
b12811 S by Me || W| 2-42
811$12 $11
Ignoring the constants and margins, the generalization error will be:
bn log( G max(co, ei)) [ 2 + ||
Vm
Apart from its dimension dependence, both norms || 2-12 and || 12,1 are bigger than ||w=|| used in our bounds. Therefore, our bound is tighter. However, they consider more general and exhaustive scenarios, including deep networks with residual connections and general Lipschitz activations.
49

---

Published in Transactions on Machine Learning Research (01/2025)
Comparison with Wang and Wu (2023). In Wang and Wii 2023 they study the same set of problems as ours, related to locality and weight sharing, but from different perspectives. First, the approximation theory perspective, studying the class of functions model can approximate, is complementary to our paper on the generalization error using statistical learning theory. The learning theory part of the paper is focused on a particular 'separation task' (see (5)) with a fixed input distribution. They also use Rademacher complexity but bound with covering number. We work with general input distributions and arbitrary tasks. Besides, our bounds are dimension independent, while their bound explicitly depends on the input dimension, an artifact of using covering number for bounding RC.
Comparison with Li et al. (2021). - In Li et al 22021) the authors consider the sample complexity of convolutional and fully connected models and construct a distribution for which there is fundamental gap between them in the sample complexity. Their analysis is based on the VC dimension and uses Benedek-Itail lower bound. Their final bound is, therefore, dependent on the input dimension. In contrast, one of the main interests of our paper was to explore dimension-free bounds. We additionally study the impact of locality and weight sharing.
J.1 Regarding Norm-based bounds and Other Desiderata of Learning Theory
Dimension Free and Norm Based Bounds. Dimension-free bounds are interesting because they hint at why the generalization error is unaffected by over-parametrizing the model. In this sense, the notion of dimension refers mainly to the input dimension, the number of channels, the width of a layer, and the number of layers. The same motivation existed for obtaining norm-based bounds for RKHS SVM models. The works of Golowich et al. (2018) and Vardi et al. (2022) are two recent examples, with the former work providing an extensive review of other dimension-free bounds. Choosing proper norm to get dimension-free bounds is one of the main questions in learning theory. Naturally, this is casier to get for larger norms like Frobenius norms, and the question is if we can have similar dimension-free results for smaller norms like spectral or, as we show in the paper, the norm of effective parameters.
Tighteness of Rademacher Complexity. In the literature around deep learning theory, there are many works questioning the relevance of classical learning theoretic results, for example, using Rademacher complexity, norm-based bounds, and uniform convergence. We can refer, for example, to works such as Nagarajan and Kolter (2019); Jiang et al. (2020); Zhang et al. (2017): ; Zhu et al. (2021. It is fair to ask if Rademacher complexity analysis, in light of these criticisms, can provide tight bounds for our case. First of all, the preceding works focused on seate-of-the-are deep neural networks with large number of layers. Our study is limited to single-hidden layer neural networks. Second, Rademacher complexity is indeed tight for support vector machines Steinwart and Christmann (2008); Shalev-Shwartz and Ben-David (2014); Bartlett and Mendelson (2002). If we fix the first layer of our network and only train the last layer, then we have a linear model, and it is known that training it with Gradient descent will lead to minimum f2-nrr solutions. For this sub-class of learning algorithms, the analysis boils to previous works on minimum norm classifiers as in Shalev-Shwartz and Ben-David (2014) for which the Rademacher complexity analysis is tight. Therefore, we believe that Rademacher complexity can still be relevant tool for shallower models, including those discussed in this paper.
Implicit Bias of Linear Networks Previous works also tried to characterize the effect of equivairance on the training dynamics. Lawrence et al. (2022) showed that deep equivariant linear networks trained with gradient descent provably converge to solutions that are sparse in the Fourier domain. While this work focuses on the effect of equivariance on optimization, the authors suggest that this implicit bias towards sparse Fourier solutions can be beneficial towards generalization in bandlimited datasets which is common for non-discrete compact groups such as rotation groups and a common assumption in steerable CNNs. Similar results were also previously obtained in Gunasckar et al. (2018) for standard convolutional networks, which can be seen an instance of GCNN with discrete abelian groups
Discussions on the Limitations. This paper provided a Rademacher complexity-basee bound for single- hidden layer equivariant networks. We obtained lower bound, which showed the tightness of our analysis.
50

---

Published in Transactions on Machine Learning Research (01/202))
conv
RT 7
Rm 2
C
conv *
Figure 5: Graphical representation of the equivariant linear projection used to preprocess the image data. An example image is projected with single filter rotated 8 times and mirrored and rotated 8 more times. The output is a 2 = 16 dinensional vector representing signal over G Dg. A rotation mirroring of the input image results in a periodic shift or permutation of the output channels.
The numerical results showed compelling scaling behaviors for our bound. However, there is still a gap between our bound and the generalization error. We conjecture that the gap is related to the idea of implicit bias. We conjecture that stochastic gradient descent training implicitly biases toward only subset of the hypothesis space even smaller than norm-bouned functions. It is an important next step to tic these two analyses hogether by characterizing the implicit. bias, for example, in terms of some kind of norms, and then using Rademacher complexity analysis to find a bound on the generalization error based on the implicit bias.
On the other hand, we provided lower bound on the Rademacher complexity. would be interesting obtain such bounds by finding the fat-shattering dimension. If two points in the dataset be transformed into each other by the action of group G, then the space of G-invariant functions cannot shatter such datasets. Therefore, the data points should be picked on different orbits they can be shattered. Such construction will be interesting in the future.
Experiment Setup
To pre-process the MNIST and the CIFAR10 datasets, we first create single D32 stecrable convolution layer with kernel size equal to the images' size, one input channel and 100 x Daaal = 6400 output channels. In particular, under the steerable CNNs framework, we use 100 copies of the reguler representation of the group D32 as output feature type. Alternatively, in the group-convolution framework, this steerable convolution layer corresponds to lifting convolution with 100 output channels, mapping a 1-channel scalar image to a 100-channels signal over the whole R D32 group; because the kernel size is as large as the input image (because we padding), the spatial resolution of the output of the convolution is a single pixel, leaving only feature vector over G D32.
This construction guarantees that rotation of the raw image by an element of Daz (and, therefore, of any of its subgroups) results in corresponding shift of the projected 100-channels signal over D
Fig. 5 shows an example of an input image projected with single filter rotated times and mirrored and rotated more times (i.c. encoded via = Dg stcerable convolution). The output is a 8-2 16 dimensional vector representing a signal over Dy. rotation or mirroring of the input image results in periodic shift permutation of the output. channels.
51

---

Published in Transactions on Machine Learning Research (01/2025)
0.020
log
0.018
0.016
MrMb
mm
14
0.014
Cy
Du
0.012
0.010
-0.010
-0.005
0.000
0.005
0.010
0.015
Generalization Error
Figure 6: Subset of Fig. 2e focusing the models training with the largest dataset size 25600. The models using the smallest equivariance groups show increased norms.
Finally, to avoid interpolation artifacts, we augment our dataset by directly transforming the projected features (which happens via simple permulation matrices since the group Da2 is discrete), rather than pre-rotating the raw images.
Our equivariant networks consist of linear layer (i.c. a group convolution), followed by a ReLU activation and final pooling and invariant. linear layer in eq. 3 All MNIST models trained using the Adam optimizer with learning rate of le 2 learning rate of le - 3 for 50 epochs. Preciscly, we use the MNIST12K dataset, which has 12K images in the training split and 50K in the test split.
2 for 30 epochs, while the CIFAR10 models are trained using with
All experiments were run on single GPU NVIDIA GeForce RTX 2080 Ti.
52


Reviews:
[{"review_id": "xyDmcKqunI", "reviewer": "Reviewer_vmUN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Positives:\n\n - Tackles an interesting and important question.\n - From what I can tell, the results appear correct.\n - The paper is mostly free of typos and errors and the presentation is done carefully (but see below).\n\nWeaknesses:\n\n - The three main theorems seem to all be relatively simple extensions of the same basic result? There is a lower bound, but this appears already known.\n - The result appears to be mostly a kind of normalization: basically the product of the input magnitude, and the norms of the various operations of the block layers. These terms kind of have to feature (by simple Lipschitz continuity-type argumnts), and the relevance of dimension-free bounds is discussed mostly in an appendix.\n - The presentation seems quite inefficient: a lot of the real estate is devoted to laying out a powerful and general notation that, ultimately amounts to linear operators.\n - There are not really pedagogically useful examples, diagrams, or experiments to help engage readers not already very invested in the question. There is probably too much detail in areas, e.g. can the abstract group-theoretic stuff be moved to an appendix?\n\nConclusion: By its nature, the quality of this paper hinges entirely on the importance of Theorem 4.1, and I am sadly not familiar enough with the literature to judge this. My best-effort conclusion is that it's a nice result, but not the sort of high-impact finding that can carry a paper alone. I recommend that the authors either (1) make it clearer that the result advances the field via pointing to existing, open questions that it answers, or else (2) further develop consequences of the analysis to make the utility of the finding more evident and applicable (whilst addressing some problems). More concrete ideas follow. I do not recommend for publication currently, though if reviewers more expert than me find Theorem 4.1, this critique does not follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Characterizes a class of models with given weight matrix norms, 1-Lipschitz constant, and positively homogeneous activation, for which it is possible to bound the Rademacher complexity by a value proportional to the product of the input magnitude bound, the magnitude of the weight matrix, and the magniude of the aggregation of the pooled values, divided by the square root of the data size. Towards the end, there is a slight generalization to include a notion of locality. Finally, there is a very brief experiment on a MNIST-like dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Suggestions for improvement:\n- Give a generalization of the result beyond one-hidden-layer networks, even if quite naive. Obviously it's great to motivate the result with a simplified result, but the message would be more compelling if accompanied by some intuition for how it actually works (even if not even close to optimal -- anyone theoretical enough to appreciate this paper would have some intuition for translating simple bounds).\n - The entire paper is phrased in quite image-centric language (filters, convolutions, etc.), and yet the only demonstration of the idea is on MNIST. I would love to see a demonstration of the idea on RGB images, even just CIFAR10. For example, a few pictures showing rotated, permuted entries to some patch and the sensitivity of the block action could be pedagogically interesting.\n- Develop everything first in a simple ReLU (or other whatever activation is easiest) + max pool and average pool framework, without needing to talk about Abelian groups or irreps, etc.\n- The experiments are, I am sorry to say, very confusing. I'm expecting bounds to be some sort of line, all I see are a bunch of similarly-colored dots that kind of have some order? But not completely since there's 2 - 12, but also C_N, etc. Figure should stand on their own mostly, and these totally do not. I'm lost from the first sentence of the description (cyclic and dihedral groups? I kind of figure it out later, but a rocky start.), and I don't know what the MNIST data set is, what a steerable convolution is, etc.\n - Ideally there would be a truly simple \"validation\" of the bound where there is some toy class of problems where the bound is tight, and loosened. Then perhaps some empirical examination in a simple, but fully-featured problem, that does not artificially preprocess the data, or whatever (e.g. it follows some standard pipeline like a PyTorch example or minGPT). It's a real shame for nice theoretical work to be torpedoed by unconvincing experiments, so please don't skip out on this section!\n- The abstract promises a careful analysis of weight sharing, equivariance, and locality, but I'm not sure I really see it in the results. If, indeed, there's a complete decomposition of the additivity of each effect, it would be good to perhaps have a table where examples of the presence and absence of each are given, along with the corresponding result. This table could also include existing results, for example it seems like the bound being dimension-free is important, and why this is so should not be in appendix J!\n- Related to the above, I would quite love to see a concrete motivation, such as the following: a generate data from a known distribution exhibiting weight sharing, equivariance, and locality and show how a model that takes account of these structures indeed generalizes better. Then tie the results to these illustrative examples. E.g. perhaps some of the examples could be constructed to obtain the upper or lower bounds.\n- There are some jolting inconsistencies in the level of detail shown in different areas of the paper. Altogether it is mostly free of typesetting problems and typos, it develops in great detail notation and foundational concepts, and appears to not take shortcuts. But at the same time, fundamental notations like $\\mathcal{L}$ and $\\hat{}$ that make up the core of the main result are not introduced previously. Even if I already know about Rademacher complexity bounds, the lack of details is noteworthy.\n- What are the issues of extending the single-layer results to multiple-layers? Obviously fine to only have results for one layer, but they should be accompanied with a prominent discussion of how and what changes for the more general situation.\n\nOther quick wins:\n- I prefer the term \"positively homogeneous\" function, since \"positive homogeneous\" is most naturally parsed as \"a homogeneous function that is positive\".\n- \"parameterize\" and \"parametrize\" are both used -- should be uniform.\n- Typo \"homoegenous\" on page 2.\n- I don't think that Figure 1 pulls its weight -- I'm obviously used to seeing diagrams like this, but usually when the visuals say something much more clearly than equations or words. I don't think that's the case here.\n- We obtain a similar norm-based bound??? for general... [page 2]\n- Group Convolutional Neural Networkss [page 1]\n- I think it is well understood that the norm of an operation may be much lower than the condition number of its implied matrix (e.g. \"Operator norm inequalities between tensor unfoldings on the partition lattice,\" by Wang). For example, I discovered this in just playing with spectral normalization in PyTorch. See E. K. Ryu, J. Liu, S. Wang, X. Chen, Z. Wang, and W. Yin. \"Plug-and-Play Methods Provably Converge with Properly Trained Denoisers.\" ICML, 2019.)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "o3ksnfvWAH", "reviewer": "Reviewer_Vs27", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The generalization trade-off between equivariant vs. non-equivariant neural networks is an interesting topic. New results can potentially interest a large community of researchers.\n2. The paper is comprehensive and includes introductions to equivariant neural networks and Rademacher analysis in the appendix, making it quite self-contained.\n\n### Weaknesses\n1. The relation of the presented bounds to prior work could be made more explicit. For instance, it would be helpful to write out what the corresponding bound to Thm 4.1 is when $\\mathbf{W}$ is not assumed to be convolutional.\n\nFurther, I have a couple of specific questions that I would like to ask the authors to clarify:\n\nQ1. In general, I have difficulty understanding the benefits of using norm-based bounds for weight-sharing. Weight-sharing typically reduces the number of trainable parameters but not the norm of the expanded weights. In my understanding, it is the norm of the expanded weights that matters in the end (as also discussed under \"Average pooling.\" on page 5), so it seems like these bounds do not use the weight sharing. Can the authors clarify this?\n\nQ2. A follow-up to the previous question. If we do not assume a convolutional structure on $\\mathbf{W}$ and instead assume something like $||\\mathbf W|| \\leq \\sqrt{|G|}M_2$, do we get the same bound as in Thm 4.1 using the technique from Golowich et al. (2018)?\n\nQ3. Do the plots in the experiments show more than the fact that the generalization error goes down as the number of training samples increases?\n\nQ4. The paper builds on the prior works by Golowich et al. (2018) and Vardi et al. (2022) where results are presented in terms of Rademacher complexities. In the present paper, the Rademacher complexities are processed with standard techniques (Thm B.3) to obtain generalization bounds. Is there a reason for deviating from prior works and not presenting bounds in terms of Rademacher complexities?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies Rademacher complexity based generalization bounds for 1-hidden layer neural networks whose input is a signal over a group G. Bounds are given for group convolutional layers, layers with weight sharing, and group convolutional layers with localized convolution filters. The bounds are dimension free and independent of the size of G.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I request the appropriate changes according to the answers to my questions above.\n\nMinor changes:\n1. Unless I missed it, it seems like $m, \\mathcal{L}, \\hat{\\mathcal{L}}$ were not defined prior to their use in Thm 4.1.\n2. A visualization of the weight-sharing in equation (5), similar to equation (2) would be helpful.\n3. `\\eqref` is more appropriate than `\\ref` for referring to equations.", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CgT0zP6YHu", "reviewer": "Reviewer_Gyfb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper provides a thorough theoretical examination of one-hidden-layer networks, leveraging Rademacher complexity analysis to derive generalization bounds. The derivation of generalization bounds that are independent of input or output dimensions is particularly noteworthy. This feature makes the findings applicable across a wide range of network configurations.\n\nThe comparison of generalization benefits across equivariant, weight-sharing, and local filter architectures enriches the understanding of their relative contributions. By offering insights into how these architectural choices affect sample complexity, the paper helps bridge theoretical analysis and practical design decisions in neural network architecture.\n\n\nWeaknesses:\n\nWhile the theoretical findings are robust, the paper lacks sufficient empirical validation to support its claims. Although some numerical results are mentioned, these are not extensive or detailed enough to show how the theoretical bounds hold in practice for varied datasets or tasks.\n\nThe analysis is restricted to one-hidden-layer networks, which may limit the applicability of the results to deeper architectures that are more common in practical machine learning. \n\nThe trade-off discussion between locality in spatial and frequency domains could be expanded with more intuitive examples or empirical support to highlight its practical significance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper examines how certain design features—equivariance, locality, and weight sharing—impact the sample efficiency of one-hidden-layer neural networks. Using statistical learning theory, the authors find that these features can improve generalization, leading to smaller sample requirements. They derive bounds that are independent of network size, relying only on the filter norms. The study also highlights a trade-off in generalization based on whether filters are defined in spatial or frequency domains, especially for band-limited data. These insights offer guidelines for building more sample-efficient neural networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "If possible, adding diagrams or brief explanations of key ideas (such as the trade-offs in locality and frequency domain analysis) could make the content more accessible.\n\nExtending the analysis to deeper architectures, or at least discussing the potential implications for such networks, would make the paper more relevant to current machine learning practice.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates the generalization properties of 1 hidden layer neural networks, specifically focusing on how architectural choices like equivariance, locality, and weight-sharing impact sample complexity (as in convolutional networks).

The reviewers generally agree that the paper is technically sound and the results are correct. However, they have raised several concerns and suggestions to improve the paper. The authors made changes in response: improved presentation by moving some of the group-theoretic discussion to the appendix; included more concrete examples and diagrams; further explained the impact of locality on the generalization error. Additionally, concerns were raised about the limited empirical validation, and the restriction to one-hidden-layer networks. The authors added new experimental results that seem to be consistent with the theory, and included new theory for multi-layer equivariant networks (which, unlike in a 1 hidden layer case, has dimension dependence).

Some of the suggested edits for the final version: 
 - Be more upfront about the limitations of the dimension-free bounds: acknowledge the mild dimension dependence in some cases and discuss its implications.
 - Expand the discussion of multi-layer networks: provide more insights into the challenges and potential approaches for analyzing deeper architectures (similarly, for max-pooling).
 - (related to the point above) Discuss the (lack of) susceptibility of this work to uniform convergence (UC) failures: the work by Nagarajan and Kolter points out the limitations of UC approaches for studying generalization in deep learning, include a discussion on how this paper circumvents the roadblocks of UC, at least in the one hidden layer case.
 - Expand related work section: the part discussing papers on generalization of convolutional neural networks should contain more details on related approaches. Right now it barely mentions some keywords, without making any connections to the current submission.
Decision: Accept (poster)