On the VC dimension of deep group convolutional neural networks
Authors: Anna Sepliarskaia
Sophie Langer
Johannes Schmidt-Hieber
Venue: NeurIPS 2025 poster ()
Keywords: VC-dimension
generalization error
group convolutional neural networks
Primary area: theory
TL;DR: We derive new VC dimension bounds for deep GCNNs, revealing how their architecture—not just equivariance—affects generalization.

Abstract: Recent works have introduced new equivariant neural networks, motivated by their improved generalization compared to traditional deep neural networks. While experiments support this advantage, the theoretical understanding of their generalization properties remains limited. In this paper, we analyze the generalization capabilities of Group Convolutional Neural Networks (GCNNs) with the ReLU activation function through the lens of Vapnik-Chervonenkis (VC) dimension theory. We investigate how architectural factors—such as the number of layers, weights, and input dimensions—affect the VC dimension.
A key challenge in our analysis is proving a lower bound on the VC dimension, for which we introduce new techniques, establishing a novel connection between GCNNs and standard deep neural networks. Additionally, we compare our derived bounds to those known for fully connected neural networks. Our results extend previous findings on the VC dimension of continuous GCNNs with two layers, offering new insights into their generalization behavior, particularly their dependence on input resolution.

On the VC dimension of deep group convolutional neural networks
Anna Sepliarskaia Booking.com .om com
Sophie Langer Faculty of Mathematics Ruhr University Bochum Universitätsstraße 150 44801 Bochum, Germany s. s.langer&re @rung.rrrub..... de
Department Applied Mathematics, University of Twente Drienerlolaan 5 7522 NB Enschede, Netherlands a aaapllaarsaaaa@utteeee.
Johannes Schmidt-Hieber
Department of Applied Mathematics
University of Twente Drienerlolaan
7522 NB Enschede, Netherlands
a. J. htt.ta/dddd..beeeereteeeetee....
Abstract
Equivariant neural networks outperform traditional deep neural networks a number of tasks. The theoretical understanding of their generalization properties remains, however, limited. In this paper, we analyze the generalization capabilities of Group Convolutional Neural Networks (GCNNs) with ReLU activation function through the lens of Sepnik-Chervoneniis (VC) dimension theory. By deriving upper and lower bounds, we investigate how the network architecture affects the VC dimension.
Introduction
A central challenge in machine learning is selecting model that generalizes well, meaning models that maintain high performance on both training and unseen data. neural networks, a common strategy to enhance generalization is to explicitly incorporate task-specific symmetries into the network architecture, as is done in Group Convolutional Neural Networks (GCNNs). Therefore, understanding the theoretical aspects of generalization is particularly important for GCNNs thinss is the problem we address in this paper.
GCNNs were first introduced by [10] to improve statistical efficiency and enhance geometric reason- ing. Since then equivariant network structures have evolved to support equivariance on Euclidean groups 6 5 B3), compact groups [18] and Riemannian manifolds 34. More recent architectures
have even been generalized beyond other types of symmetry groups [35
27]. GCNNs have
demonstrated promise in a variety of domains, including fluid dynamics 132 31, electrodynamics
(35). medical image segmentation (6), partial differential equation (PDE) solvers [8), and video tracking 29). A notable example of the success of equivariant neural networks is the AlphaFold algo- rithm, which achieves high accuracy in protein structure prediction through a novel tro-trransltiion equivariant attention architecture of the neural network [15] 14]
While GCNNs have demonstrated strong empirical performance often outperforming Deep (Feed- forward) Neural Networks (DNNs) rigorous theoretical guarantees remain limited. This gap is due a lack of interest: indeed, several works have attempted address the theoretical under- standing of GCNN's generalization. Most of these studies approach the problem by comparing the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

generalization behavior of equivariant neural networks to that of models without built-in symmetries 7 24
25 28 While these works offer valuable insights, they typically do not account for the specific GCNN architecture and are instead applicable to general equivariant or invariant classifiers. contrast, our work provides generalization bounds for GCNNs that explicitly account for the number of layers, the number of weights, and the input dimension.
12
26
Recent works that study GCNN generalization for given architectures are, to the best of our knowledge, limited to two-layer networks 4 21. Our analysis extends this to GCNNs of arbitrary depth.
To study the generalization properties of GCNNs, examine the VC (Vapnik- Chhnnl--cervonekkss dimen- sion, the pseudo-dis diuund-- and the fat-shattering dimension classical measures from statistical learning theory that quantify the capacity of a model class to fit arbitrary labelings. For example, class that can realize all labelings of n points has VC dimension at least n, while a class with only two different functions has VC dimension 1. Recent work has revived VC-based analysis for modern network architectures, including GCNNs 13 21 convolutional neural networks (CNNs) [7]. and DNNs (3].
2 Results
The main result establishes upper and lower bounds on the VC dimension of GCNNs with ReLU activation function. Let Hw,,, and Fw.L denote the classes of GCNNs and DNNs, with ReLU activation function, number of weights W, depth L,, and r the group size in the GCNN. We prove that under the assumption I. < W0.99 there exist constants c, C>> 0 such that
of (C((F..)) + W (r)) S VC(HW.L.)) S ((VC(FW.L) + LW (r)).
While we have not made an attempt to optimize the constants in the inequalities, Section C shows that if additionally W > 2 and W 125, one can take 1/7500 and C 500.
This result demonstrates that, contrary to previous intuition. the class of GCNNs richer than the class of DNNs with the same number of parameters, The difference in capacity can be expressed as a logarithmic function of the group size, with a larger group size leading to a more pronounced difference between the two classes. In the limiting case r + co, the VC dimension of GCNNs diverges to infinity. Importantly, the analysis does not depend on the specific structure of the group and therefore applies to both continuous and compact Lie groups
The analysis also naturally extends the fat-shattering dimension, which measures how many points can be separated with a given margin, and thus additionally captures robustness of the classifier. For model classes that are closed under positive scaling, the fat-shattering and pseudo-dimensions coincide (see Theorem 1 11.14 14 in IT). Since ReLU activations are positively homogeneous, that is, scaling the output of the final layer scales the entire network output, the GCNNs we consider are closed under positive scaling. Consequently, the generalization bounds derived in this paper for the pseudo-dimension also apply directly to the fat-shattering dimension.
Whereas the ReLU activation function the running example, the inequalities hold under broader conditions the activation function stated here (the constants c, C do depend, however, the activation function). As the proof of the upper bound follows the strategy in [3], the same assumptions appear. The lower bound holds if DNN with this activation function can approximation the indicator function on an interval.
Assumption 1 (Requirement for the upper bound). The activation funivationnuunctinnn is piecewise polynomial. Assumption 2 (Range of activation functions for the lower bound). For any A < B and e > 0, there exists a DNN i satisfying
f1, [1, if B-c, [A B+c..
{b.
I(x) (0, 0. if
These assumptions imply that the same bounds hold for the Leaky ReLU (x)+ max(x, oz), with 0 < a < 1 the Leaky ReLU parameter. Indeed, the Leaky ReL. is piecewise linear with two linear segments and therefore the upper bound applies. For the lower bounds, it is sufficient to check

---

that DNN with Leaky ReLU activation can approximate the indicator function on [A, B] using
[A, = (1 axe (A - -e))+aa - (a- -A+,a - ((x (B -E))+.o - (o B)+
where 6 O, and < B -
For general smooth activation functions, however, the current proof strategy does not extend directly, For instance, the case sigmoidal networks, a lower bound appears feasible because such networks approximate indicator functions (see, e.g., Lemma 4 in (T9].. In contrast, the upper bound does not follow readily: the region-counting argument, which applies to networks with piecewise polynomial activations like ReLU, fails for sigmoidal activations due the absence of polyhedral decision boundaries.
Finally, to complete the comparison between the generalization bounds of GCNNs and DNNs, we also analyze the VC dimension of GCNNs with group size r and DNNs when both architectures have the same number of neurons per layer. In this setting, GCNNs benefit from weight sharing across group elements, which reduces their number of parameters by factor of 72 compared to DNNs (see Section 4.2) We show that, under these conditions, the VC dimension of GCNNs is reduced proportionally to the group size r.
3 GCNNs
3.1 Group theoretic concepts
GCNNs capture symmetries in data via group theory. A group is set equipped with an operation such that h. g E implies hog E G; there exists an identity element e E G such that eog = goe = for all g G: there exists inverse element g
such that g g = g o e; and for any
h. E G, we have (g o h) o i = (h i).
A group action describes how group interacts with another set. More specifically, an action of G on a set is map o : G x X - X' such that for all gl. G and for all æ E X
(g192) c x gi o (g2 x))
On the functions ( RJ, the left regular representation of group is the action
(go f)g') = f(g for any g.g E G.
(2)
For so-called kernel function K.: G + R and function f + R, the group convolution of KC with f at an element g E defined as
(K f)) - K(g K(g '6) f(g') du(g'),
(3)
with μ being the Haar measure [23 Theorem 8.1.2]. The Haar measure is a unique left-invariant measure that exists for all locally compact groups (see (30] Definition 1.18]). For the integral in (3) to be well-defined, we assume that both, the signal f and the kernel K,, measurable and bounded.
The group convolution computes weighted average over the group elements. It equivariant with respect to the left regular representation of G defined in that is, o (KC any group element g.
(K * (g f)) for
In the case where G is a finite group, the group convolution becomes the sum
(K * (1) = G
Σ k() -(g')) E'EG
In practice, continuous groups such as rotations or translations are often discretized, and computations are performed on finite grids. This discretization process involves approximating the group G by finite subset
GT = {g1, ... }
We refer to the cardinality the resolution of the discretization.

---

Let L be the number of GCNN layers and assume that the respective numbers of GCNN units in the layers 1,... L is denoted by m.,, m.. To derive recursive formula for the GCNN, we denote the inputs of the GCNN by ho, ..... ho Note that they are also assumed be functions For example, for the group formed by all continuous rotations, the discretization selects a finite number of rotation angles. For the translation group, discretization consists of finite number of shifts.
After discretization, the group convolution operates this finite set. Ignoring the reweighting it is then given by
(K* f)( Σ K(g 9;) f(g)).
(5)
This operation is called G-correlation Note that (K ())== =r- (K+g). I)
with
the identity element of the group, then, on G", K f= The G-correlation heavily depends on the discretization of the group and can differ significantly from the integral version (3). However, both
definitions become approximately the same (up to rescaling) if the elements 9j are drawn from the
Haar measure. In the case of GCNNs, the discretization is determined by the structure the data.
3.2 GCNN architecture
To parametrize the kernel function, let
Kg G I.
L....,k
(6)
be a set of basis functions. The kernel functions Kew are then expressed as linear combinations of these basis functions, that is,
Kw
WgKst
where w = (wi,..., wx) is the vector of trainable parameters.
Given activation function
R, group convolutional unit (GCNN unit) G-convolution
takes an input function on the discretized group f = (ff,..., fmg))" G" - 1 as input and outputs another function on the discretized group G + IR. The output h is
h= a ② Kw, * fi f-bb) b).
(8)
with the group convolution operation defined (5). The weight vectors Wi...., Wm and the bias b are parameters that are learned from the data. In line with the common terminology, we refer to the output as feature map.
GCNN layer (also called G-convolutional layer or G-conv layer) computes several GCNN units in parallel, using the same input functions but applying different kernel functions (also known as filters), each with potentially different parameters. Specifically, a GCNN layer with M units and input function (fi...., .m......''' G" "R, computes the following M functions
h4 = a Σ Kw * fi
bb:) -b)) j= l
where Kw., connects the i-th input with the j-th output. The trainable parameters in the GCNN layer are the weight vectors Wij and the biases by. As other network architectures, GCNNs are typically structured bierarchically, with several GCNN layers followed by fully connected layers. We assume that the input of the first GCNN layer are already functions on the discretized group.
G + R. If for given 0. L 1, he,r,..., he,m, are the outputs (also known as feature maps) of the L-th GCNN layer, then, the me+1 outputs of the (e + 1)-st GCNN layer are given by
h4415 =
Σ
K w
hes - 6(0)
(10)

---

for = 1..... m4+1. The final output of the GCNN is given by
m
hr,,(g))
(11)
BEG"
which equals up reweighting global average pooling operation. As take the all group elements g. this operation makes the network invariant instead of equivariant to geometric transformation (see, e.g.,
T8 16 6)).
In this work, we consider the ReLU activation function ((x) = max 0). We denote the class of ReLU GCNNs with L layers, m, units in layer O, ....., L, k dimensional weight vectors in 7 and r the cardinality of the discretized group by
Hlk, mo. ML, r).
(12)
The learnable parameters are the vectors w (6) and the biases (0) j (= 0....., 1. During the training phase, they are updated through gradient-based optimization techniques, such as stochastic gradient descent (SGD). The updates aim to minimize an objective function, typically loss function measuring the difference between the network predictions and the true labels. While in practice, GCNN architectures also include feedforward layers, we only focus in this work on the GCNN layers.
3.3
CNNs as a special case of GCNNS
The convolutional layer in CNNs can be obtained as a specific case of the GCNN layer for the translation group T. An element t of the translation group corresponds to vector (f1, t2) R², and the group operation is defined as t o t' (t1 + t 22 + E2), meaning that one vector shifted by the components of another. The inverse of translation t is t- = (-t1, -t2), reversing the direction of the shift.
square image can be interpreted as a function on the unit square [o, 1] x [o. 1]. Setting the function values to zero outside the unit square, can then be extended to function IR Since R is isomorphic to the translation group, a square image can thus be viewed as a function on the translation group T.
To illustrate the discretization step, consider the MNIST dataset (20), which consists of grayscale images of handwritten digits ranging from 0 to 9. Each MNIST image is represented by grayscale values. This means that mo is equal to 1, as the image is characterized solely by pixel brightness. In contrast, for RGB image, my 3, corresponding to the red, green, and blue components of each pixel.
Furthermore, since the values are only 28 28 pixel grid, the translation group T is discretized by 7884 = { 28 28 i,j E [28]] } In turn, we can view an MNIST image function f on 784
The function value f( 2 is the (i,j)-th pixel value.
In CNNs, the coefficients of the convolutional filters are typically represented by s x s weight matrices, with prechosen integer. For simplicity, we consider
3 in the following. The
i = 1...., 28. For the kernel Ke (MI, U2) = Ee We+1,++1 (M1, = =(2s 28) and Si,j = (i/28, j j/28), this can also be rewritten in the form (5) via
convolutional filter computes Ei We+1k+1ff
s44 j-k) 28
(Kw * () = Σ
Kw ott.
787784
weil (11-2
l kt
)) S(t)
Σ
28
28
28
TETT
(,k=-1
itt j j+k
WEILKHIJ
28
28
Thus, in this equivalence, the kernel is a linear combination of indicator functions.
5

---

3.4 Difference between GCNN and deep feedforward network architectures
GCNNs and deep feedforward neural networks (DNNs) differ in how their computational units are defined. In DNN, each unit computes an affine transformations applied to the output of the previous layer, followed by an activation function o. If the output of the previous layer, w is a weight vector, and b bias, then unit in a DNN computes
a ( 2 b).
(13)
The class of ReLU DNNs with L layers (that is, L 1 hidden layers and one output layer), my units (or neurons) in layer i = 0, O....,L, and a single unit in the output layer (i.e., my = 1) is denoted by
Flmo....,m..)
(14)
While both the DNN class F(mo..... ... my) and the GCNN class H(k, ma, .... mL,)) share the same architectural structure and apply the ReLU activation function, they differ in their unit definition, meaning that F(mo, .... m.) uses DNN units (13) and H(k, my.... mL, r), employs GCNN units
(8)
4 VC dimension of GCNNS
We now derive upper bounds for the VC dimension of the GCNN class H(k, mo...., m,,,), We begin by formally introducing the VC dimension.
Definition (Growth function, VC dimension, shattering). Let H. denote a class of functions from F (-1,1} (often referred as the hypotheses class). For any non-negative integer m, define the growth function of H as the maximum number of distinct classifications of m samples that can be achieved by classifiers from H. Specifically, it is defined as:
[m = max
7.1
fI....I...FF EF
H can generate all possible 2nd classifications for set of m inputs, we say that H. shatters that set. Formally, if
h(fm)) HH = 2
we say H shatters the set (f.....Immk:
The Vapnik-Chee Chervonenkis dimension of H. denoted as VC(H), the size of the largest shattered set, specifically the largest m such that [1x(m) = 2m If such largest exists, define VC(H) = Do.
The VC dimension cannot be directly applied to class of real-valued functions, such as neural networks. To address this, we follow the approach in (3] and use the pseudodimension as a measure of complexity. The pseudodimension is natural extension of the VC dimension and retains similar uniform convergence properties (see (2 and Theorem 19.2 in (I)
Definition (pseudodimension,, For class H of real-valued functions, define its pseudodimen- sion as VC(H) == VC(sigu (H)), where
sign(H) (sign(H b) H H. R
where sign(a) for x > 0 and otherwise. We write Th to denote a growth function of sign (H).
For common parameterized function classes, the VC dimension is related to the number of parameters.
For DNNs, it also depends on the network depth, as discussed in 3 As proved in this paper, for
GCNNs, the VC dimension further depends on the resolution. The following result provides an upper bound on the VC dimension of the GCNN class H(k,, ma; ... mm, r) formally defined in (12). Recall that L is the number of layers, are k dimensional, and r is the cardinality the discretized group.
is the number of units in layer O.... L. weight vectors
Theorem 1 (Upper Bound). The VC dimension of the GCNN class H H(k, mo.... ML, r) is upper bounded by
UB L +++4
Σ
We
log2
Ser
mé
(15)

---

with We the number of parameters to the E-th layer, that is,
We Σ my (kmkmj-1 + 1).
(16)
The proof strategy is borrowed from
3 and the detailed proof provided the supplement.
An alternative to bounding the VC dimension based on the number of layers and neurons per layer is express the bound in terms of the total number of trainable parameters. The main advantage of this approach is that it applies to a wider range of architectures including sparsely connected GCNNs. In this context, establishes a bound on the VC dimension for the class
FW,L {F F | S L, WI( S W
(17)
consisting of DNNs with most L hidden layers and overall number of weights W. Similarly, we consider the GCNN class:
HW.L.r (H((k, .......,T.. m., r) l S W. S W)
(18)
consisting of all GCNN architectures with a total number of parameters bounded by W, depth at most L, and r the cardinality of the discretized group. The following theorem provides a lower bound on the VC dimension for this class:
Theorem 2 (Lower bound). If W, L> 3, then there exists a universal constant e such that
VC(Hw.L.r) 2 cmax(VC(Fw.L).. W (rg)(r)}.
The proof this theorem is particularly challenging and requires novel techniques. Standard approaches used for DNNs cannot be directly applied, as the second term in the lower bound depends on the cardinality the group-an aspect unique to GCNNs. Unlike DNNs, where the VC dimension is determined solely by the number of parameters and layers, GCNNs introduce dependency on the input dimension. To overcome these challenges, we establish new connection between GCNNs and DNNs and show how the structure of GCNNs allows indicator andcator-based functions to shatter [log2(r) (r)] input functions. A proof sketch is provided in Section 6 with the full proof detailed in the supplement.
additional
4.1 Analyzing the tightness of bounds for GCNNs
To compare the upper and lower bounds, we first establish a connection between the VC dimensions of DNNs and the upper bound for GCNNs, as VC(Fw.L) appears in the lower bound. For this, we rely on the VC dimension bound for DNNs with piecewsee-polyoone
activation functions, derived in Theorem 7 of [3]. Specifically, we focus the class of DNNs with L layers and m. units in layer
i, as defined in (14). This network class corresponds the case where
and p = Theorem 6 of [3] By applying the inequality log, (log, (x:) I (x), which holds for any 2 2, the VC
dimension bound for this class simplifics to
Σ Wi(F)) log2 E=1
=B(F)= =
4e
Li
where F is shorthand for F(mo. mL). Here, WiFF) represents the number of parameters in F up to the i-th layer, given by
W((F) = Σ m +1.
(19)
Comparing (6) and (19), and assuming equal number of computational units per layer in both GCNNs and DNNs, we observe that the number of parameters in GCNNs satisfies the incquality
W; < (F), where & the dimension of the weight vector w in 7 Combining this with the bound in Theorem I we obtain
UB(H) S 2UB(F) + Ewacrr) 12g)(2r).
(20)
8=1
Combining this inequality with the Eq.
41
arrive at the following result.
7

---

Corollary 1. W is the total number of parameters and L the depth of the network, with L < W0..00 then there exists a universal constant C such that VC(Hw,,.r)) S (VC(Fw..L) + LW (r))
By combining Corollary with Theorem 2 derive the bounds presented in ① In this setting, the difference between the upper and lower bounds on the VC dimension is at most a factor of L. Closing this gap is challenging problem, but conjecture that the lower bound could be improved. Our intuition stems from the fact that the upper bound is derived using a parameter-counting argument, closely following the approach in (3. In that work, it was shown that when using a parameter- counting argument, the lower bound could be achieved, at least in the case of DNNs. This suggests that fully close the gap, either the proof technique for the upper bound must be fundamentally changed, or a different example must be constructed to strengthen the lower bound.
In practical applications. GCNNs tend to have relatively small depth. For example, GCNNs use 7 layers for the rotated MNIST dataset and 14 layers for CIFAR-10 (9. In this regime, the derived upper and lower bounds on the VC dimension are nearly identical, further supporting the practical tightness of the results.
4.2 Comparison of VC bounds for GCNNs and DNNs
Equivariant neural networks are expected to have lower sample complexity than DNNs without built-in symmetries, i.c those represented by F, := F(rmo..... .rmm)...,,m..)... where each layer has rm; units. As shown in the following lemma, compared to DNNs, GCNNs reduce the VC dimension and consequently the sample complexity proportionally to the group size r. This finding is consistent with previous work
24
Lemma 1. For neural network with L layers and W weights satisfying L < (F.)) there
exists c > 0 such that for the GCNN class H. := H(k, mo.....mmp.............. r), the VC dimension satisfies
VC(M) - c VVCFF)
(21)
Proof. The dimension k of the linear space generated by GCNN filters is bounded by r, as functions on G" lie subspace determined by the identifiers of g E G", For DNNs where L W WFF))0.99) (W(FF)FF) (F,)), where W(F,) represents the number
the VC dimension scales as (CF)F) x
of parameters in F,.. Using Eq. (16). we obtain
L Σ 1--1
x
=
rme(rme-1+ + L Log
Crme(rme-1
rme(kme- +1)
L Loog Σ rmo(kme-1+1))
+
-r -r (rW
(0(BB(A)
Taking into account that (BH) Z VC(H), we obtain the claimed inequality 21
A different but relevant comparison considers GCNNs and DNNs with the same number of parameters. As stated in Theorem (2) in this case, the VC dimension of GCNNs is larger than that of DNNs. The difference lies in the scaling terms W log(r) and W L log(r) between HW, and Fw,L-
Novelty compared to related work
In this section, we compare our contributions to the most relevant works on the generalization of neural networks. First, we consider (3) which analyzes the VC dimension of DNNs. While their results provide valuable insights, they do not account for the dependence the resolution of the group acting on the imput data. One of the contributions of our work is showing that the VC dimension of GCNNs depends logarithmically
r, feature unique to GCNNs and absent in 3
For the special case of = and W 2, the results scale as log(r), aligning with the findings of (21). However, significantly extend these results to more practical settings, including deeper
8

---

architectures (L > 1) and larger parameter counts (W > 2), making the findings more applicable to real-world scenarios.
Finally, [26] studies the sample complexity of data augmentation and compares it to learning without augmentation. While their work is relevant to transformation-iivarian learning, it does not analyze the VC dimension of neural networks. As a result, their findings address a different aspect of generalization and are complementary to ours.
Proof sketch of Theorem 2
To establish a lower bound for the VC dimension of the GCNN class, recall that Hw, as defined in (33). represents the class of GCNNs with resolution r, k the dimension of the kernel space, most L layers, and no more than W parameters. Additionally, let G" 92: : 9r be .............................
discretized group containing the identity element e.
To prove Theorem 2 we establish two lower bounds on the VC dimension of the GCNN class: one in terms of the VC dimension of classical DNNs, and one in terms of the resolution r. We then combine these bounds to obtain the desired result. Specifically, we prove the existence of universal constant e > 0 such that
VC(Hw,,,F) 2 c. vC(Fw,L);
(22)
and
VC(Hw,,,r)) 2 e W [log2 rJ.
(23)
Here, Fw.r. is the class of DNNs with at most L hidden layers and at most W weights, defined in (4).
The proofs of both incqualities rely on the relationship between DNNs and JENNSs-pecificallly that GCNN whose convolutional filters are proportional the indicator function of the identity element can be represented as DNN. This result is important by itself and is formulated in Lemma in the supplementary material. This representation further implies that in order to prove that GCNNs can shatter a set of m functions, it is sufficient to construct DNNs with the same number of parameters that can shatter ma points. This observation central to the proofs and guides the construction used in both bounds.
In both arguments, we utilize so-called indicator neural networks: DNNs with ReLU activations that approximate indicator functions over specified interval bJ. The endpoints of these intervals serve as learnable parameters, allowing the network adaptively define its support. Formally, this can be defined as follows:
a)+ + +(x 1 (x),,c)))) - (a- -x a))
(x- (b++(bb))) )))+)
(24)
with four neurons in the hidden layer and (x)+ max(x, 0) the ReLU activation function.
To prove 22 we begin by constructing new class of DNNs by adding indicator networks the original class F. which shatters VC(Fw,L.) These indicator components are designed to ensure that the resulting DNNs vanish outside a specified nigh-dimensional hypercube. This construction guarantees the existence of m functions over G" for which the corresponding GCNNs produce the same outputs as the original class F on the points it shatters.
Proof of bound (2
The combined networks use most 5W weights and retain the same depth L. Finally, fact that for any constant / >> 1, the VC dimension satisfies VC(FFw.t) 2 q VV(FF,,.) for some constant Ca 1, completing the argument. Formally, this result is stated in the following lemma. The proof is deferred to the supplementary material.
the
Lemma 2. For L let HSW.L+1.5 1.r be the class of GCNNs defined as in 33 and FW.L be the class of DNNs defined as in (34. Then VC(Hsw.Lt1.r) VC(Fw.)).
Corollary 2. In the setting of Lemma exists a constant such that VC(Hw,L.r)
if the number of layers and L W..9 then there c. vC(Fw.L).
To prove the lower bound 23 we consider a subclass of GCNNs repre- sented by indicator network. We show that functions from this class can shatter set of input
Proof bound 23

---

functions Fm (ff:G" + R with m = [log2 r by adjusting their parameters Seaamttess-seciffcallly the endpoints of a specified interval to match the values of the input functions in F...
This GCNN class uses only parameters and inherits the properties of 'indicator' networks; in particular, each function in the class outputs for any input function whose value lies outside a specified interval [A, BJ. This ensures that the GCNN only shatters functions whose values fall within that interval.
Next, we consider the sum of W "indicator' networks, each designed to shatter functions with values in disjoint intervals. The resulting
shatter the union of these functions, meaning it can shatter W [log2 r] functions in total. By choosing W 4W, conclude that VC(Hw.L.r) W [log2 r], which completes the proof.
The following lemma provides a formal statement regarding the GCNN class represented by 'indicator" networks, while the corollary presents the result for the sum of W 'indicator' networks. The proof can be found in the supplementary material.
Lemma 3. Let HA.L. be the class of GCNNs defined in (3) Then VC(H4...)) 2 (log2 T.. Moreover, for any two numbers A < B, there exists a finite subclass of GCNNs H C HA.L. that shatters set of log,
functions {fi G - [A,
I....,,..,,,,....... log,, r), and outputs zero for
any input function f G G RR [A, B).
Corollary 3. The VC dimension of the class Haw. L,,, consisting of GCNNs with 4W weights, L layers, and resolution r satisfies the inequality VC (Haw,,,)) 2 W [1og2 rJ.
By combining Corollaries and 3
we obtain the lower bound
VC(Hw, 2 max (oV(FF..)) [log21]}
thereby proving Theorem 2
7 Conclusion
In this work, we established nearly-tight VC dimension bounds for a class of GCNNs, showing that their complexity depends on the number of layers, the number of weights, and the resolution of the group acting on the input data. While GCNNs share similarities with DNNs, they exhibit an additional term, W [log, rj. which grows logarithmically with the input resolution r. This aligns with prior findings
(1 that, as r approaches infinity, the VC dimension of GCNNs becomes unbounded.
The results highlight the sensitivity of GCNNs group discretization, offering new insights into their model complexity and generalization behavior. While the upper and lower bounds are close in practical settings, gap remains, and refining the lower bound remains an open challenge.
Acknowledgements
J. S.-H. was supported in part by the NWO Vidi grant VI. Vidi. 192.021. S.L. was supported in part by the NWO Veni grant VI. Veni.232.033
References
[1] Martin Anthony and Peter L. Bartlett. Neural network learning: theoretical foundations. Cambridge University Press, Cambridge, 1999. ISBN 0-521-57353-X. doi: 10.1017/ CBO978051162480 1777805116220 11622216..
[2] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
[3] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC- dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2011, 2019.
[4] Arash Behboodi and Gabriele Cesa. On the sample complexity of one hidden layer networks with equivariance, locality and weight sharing, arXiv preprint arXi::2411.14288 2024.
10

---

[5] Erik Bekkers. B-spline CNNs on Lie groups, arXiv preprint arXiv: /909: (tte:::999..999990 /0057, 2019.
[6] Erik Bekkers, Maxime W Lafarge, Mitko Veta, Koen AJ Eppenhof, Josien PW Pluim, and Remco Duits. Roto- tnto-translation covariant convolutional networks for medical image analysis. In Medical Image Computing and Computer Assisted Ceerrention--MICCC 2018: 21st In- lernational Conference, Granada, Spain, September 16-20, 2018, Proceedings, Purt I, pages 448. Springer, 2018.
[7] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 34:1 1873-- 2021.
[8] Johannes Brandstetter, Max Welling, and Daniel Worrall. Lie point symmetry data aug- mentation for neural pde solvers. In International Conference on Machine Learning, pages 2241-2256. PMLR, 2022.
[9] Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pages 2990-2999. PMLR, 2016.
[10] Taco Cohen and Max Welling. Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pages 2990-2999, New York, New York, USA, 20-22 Jun 2016. PMLR. URL (RR[]tttss:/p/oceeiiiii
Group equivariant convolutional networks. In Maria Florina
mlr
press/v48 cttec//ccecccccc html
[11] Nima Dehmamy, Robin Walters, Yanchen Liu, Dashun Wang, and Rose Yu. Automatic symmetry discovery with lie algebra convolutional network. Advances in Neural Information Processing Systems, 34:2503 2515, 2021.
[12] Bryn Elesedy. Group symmetry in PAC learning. In ICLR 2022 Workshop Geometrical and Topological Representation Learning, 2022.
[13] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In International conference on machine learning, pages 2959-2969, PMLR, 2021.
[14] Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling, Se (3)-transformers: 3d roto-translation equivariant attention networks. Advances in neural information processing systems, 33:1970-1984 2020.
[15] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, (96(7833))5883-5888 2021.
[16] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[17] Michael Kohler and Benjamin Walter. Analysis of convolutional neural network image classifiers in rotational symmetric model. IEEE transactions on pultern analysis and machine intelligence, (9)5)5203355 2023.
[18] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning, pages 2747-2755. PMLR, 2018.
[19] Sophie Langer. Approximating smooth functions by deep neural networks with sigmoid activation function. Journal of Multivariate Analysis, 182-C:104696. 2021.
[20] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 96(11):227--233 1998.
[21] Philipp Christian Petersen and Anna Sepliarskaia. VC dimensions of group convolutional neural networks. Neural Networks, (69:462-474, 2024.

---

[22] David Pollard. Empirical processes: theory and applications, volume of Regional Conference Series in Probability and Statistics. Institute of Mathematical Statistics, Hayward. CA; American Statistical Association, Alexandria, VA, 1990. ISBN 1.940000-6611.
[23] Claudio Procesi. Lie groups: approach through invariants and representations, volume 115. Springer, 2007.
[24] Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group Invariant/quivvariant deep networks via quotient feature spaces. In Uncertainty in Artificial Intelligence, pages 771-780. PMLR, 2021.
[25] Akiyoshi Sannai, Makoto Kawano, and Wataru Kumagai. Invariant and equivariant reynolds networks. Journal of Machine Learning Research, 25(42):1-36, 2024.
[26] Han Shao, Omar Montasser, and Avrim Blum. theory of pac learnability under transformation 1-000, 2022.
invariances. Advances in Neural Information Processing Systems,
[27] Bart M. N. Smets, Jim Portegies. Erik J. Bekkers, and Remeo Duits. PDE-based group equivariant convolutional neural networks. J. Math. Imaging Vision, 65(1))209 239,,, 2023. ISSN 0924-9900.1557-77688 doi: 1...0077110851-02-0011112 N0.1007/s10551-022 022-0000085-02-11111211111--1111 01114-x
URL URL/attss:/ddi..ozz
[28] Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of
invariant classifiers. In Artificial Intelligence and Statistics, pages 1094-1103. PMLR, 2017.
[29] Ivan Sosnovik, Artem Moskalev, and Arnold WM Smeulders. Scale equivariance improves siamese tracking. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 2765 2774, 2021.
[30] Markus Stroppel. Locally compact groups, volume 3. European Mathematical Society, 2006.
[31] Ricardo Vinuesa and Steven L Brunton. Enhancing computational fluid dynamics with machine learning. Nature Computational Science, 2(6))358-3366 2022.
[32] Rui Wang, Robin Walters, and Rose Yu. Incorporating symmetry into deep dynamics models for improved generalization. arXiv preprint arXiv:2002.0306/ 2020.
[33] Maurice Weiler, Fred A Hamprecht, and Martin Storath. Learning steerable filters for rotation equivariant enns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 849-858, 2018
[34] Maurice Weiler, Patrick Forré, Erik Verlinde, and Max Welling, Coordinate independent convolutional networks-isometry and gauge equivariant convolutions on riemannian manifolds. arXiv preprint arXiv:2 2021.
[35] Maksim Zhdanov, David Ruhe, Maurice Weiler, Ana Lucic, Johannes Brandstetter, and Patrick Forré. Clifford-steerable convolutional neural networks. arXiv preprint arXiv:2402. 14730, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes],
Justification: In the abstract, we claim a theoretical result, which formally proven in the main body of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of our work are discussed through the assumptions stated in the formulation of the main theorem, which define the conditions under which the result holds.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes],
Justification: We provide the formal statement of the theorems along with the full set of assumptions. Complete proofs included in the supplementary material, and the main paper contains a high-level overview of the proof strategy.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA].
Justification:
The paper does not include experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA].
Justification:
The paper does not include experiments requiring code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
pub / gui CodeeeSSum ss aasionooolioo cy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht
cc ctappss.cc/pbbic/guuuiu
/Coee Submi s issionn ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA].
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research is theoretical in nature and does not involve human subjects, sensitive data, or potential dual-use concerns. We have reviewed the NeurIPS Code of Ethics and confirm that our work complies fully with its principles.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA].
Justification: This is theoretical paper that does not introduce new algorithm or applica- tion, and therefore does not have direct societal impact in its current form.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use package should be provided. For popular datasets, baaasstts.ppprrssesee papersswss thoode. com datasset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
assets are released,
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
cc/ Please refer to our LLM policy (https: : /ttess:///urriiie http///urriscccoonnfeeeeee ccc/oonfeeences/////oooooooocsse 2025/
LLM) for what should should not be described.
19

---

Proof. As first step of the proof, we show that any GCNN unit he,, of any layer é E (0...., L} is a piecewise polynomial of degree at most l. We proceed by induction on the A Proof of Theorem
1
Recall that
H = H(k, ,o....,
(25)
where is the cardinality of the discretized group G" {911 92.99..... :.. The parameter & determines the number of basis functions
K₃ G" R,
1,...,k. k
(26)
in the parametrization of the kernel function
Kww
WyKs.
The other parameters m...... my define the network architecture, and We represents the number of parameters in the GCNN up to layer f. The class H. consists of all functions that can be represented by neural network with this architecture.
We restate Theorem for convenience:
Theorem 3 (Theorem D. The VC dimension of the GCNN class H. H(k, ..., r > is bounded from above by
m,,,)) m.,,..,m,."
with
L
UB(H) = =+1++
Σ
We
log2
Ser
me
(27)
t=1
For the proof, we consider input consisting of functions from G" Rm denoted by
Fm = if....... fm..
(28)
To prove use the following known result:
Lemma 4. [Lemma 1, (2) Let . Pm be polynomials of degree most t depending m variables. Then
2emt
II = [isppd)((()).....spppppdld))))l) x E 2
We denote S()) the number of regions in the parameter space RW, such that in each region, the GCNN units in the 4-th layer (denoted by (ge.)(g) l S me, Fm E G"]) behave like fixed polynomial of degree at most l in the Wj network parameters that occur up to layer E.
Lemma 5. Let H. be the class of GCNNs defined in (25). with at most We parameters up to layer EE {1, ..... L}. If Fm is the class of functions defined in 28 and S()) is as defined above, then for t=
S(e + 1) 2 2eme+1mr(e+11) W
We+t
S(E).
(29)
Moreover, the GCNN units (he+1.5(g) j S m441,J E Fm,9 Gr) with heti, defined for different finctions f E Fms are piecewise polynomials of degree S 1+ 1 in the network parameters.
and j E layers f.
For the base case O, the GCNN units ho, for S mg correspond the input of the network. the inputs are independent of the network parameters, ho.j are polynomials of degree 0.
Assume the statement holds for all layers up f. We now prove it for layer f 1. The GCNN unit in layer& + 1 is defined by convolution with the feature maps from the previous layer, that is,
mg
b =
Σ
KC
1 * her5
1/4)
20

---

where the convolutional filter is expanded in terms of the fixed basis functions K, via Kww E wgKg. For fixed network parameters, 9 he. (g) is function of the group, with (g) E IR for any g E G". By the induction hypothesis, he,r(g) are piecewise polynomials degree at most with respect to the network parameters, with the polynomial pieces depending the network input and the group element g.
Next, for any input and any group element y. the term (K, (g) can be written as
(Ks (e)
Σ
Kg o o'') hea(g').
g'EGG
Since heer(g") a piecewise polynomial of degree at most E, it follows that (Kg * he)) is also piecewise polynomial of degree at most L. Thus, the convolution
(Kw hea
Σ ws * (g)))
is weighted sum of piecewise polynomials, which remains a piecewise polynomial. However, multiplying by the weights w, increases the degree of the polynomial, making it at most + Subtracting the bias term 1500 and applying the ReLU activation function may increase the number of pieces, but does not increase the degree the polynomials. Therefore, for any input and any group element 9, the GCNN unit he+1.(6 (g) remains a piecewise polynomial with degree S É + 1. This completes the proof by induction.
Next, we show 29 Each GCNN unit in layer & + 1 is computed by
Σ K w
* her
with (xx) = max(x, 0} the ReLU activation function. As mentioned above, applying the ReLU function can increases the number of regions in the parameter space where the GCNN units behave as polynomials. This occurs, as the ReLU function either outputs the input itself (for positive values) zero (otherwise). As result its application decomposes each of the S(L) regions of the parameter space in layer l in multiple subregions. To bound this number of subregions, we need to count the number of possible sign pattern that arise after applying the ReLU activation.
Fixing one of the S(E) regions of layer f, by definition, all functions he);(g) are polynomials in the parameters of degree at most t. Each of the m1+1 GCNN units in layer & + 1, is then also polynomial of degree at most & + 1, leading to at most m4+ yrr polynomials, where m is the number of input functions defined in (28) and is the resolution. Applying Lemma to the m m4+1mr polynomials degree = + depending on n We+1 parameters leads to at most
2eme+ 1mr + 1) 2
Wett
W
different sign patterns for each region of S(E). This shows
29 and concludes the proof.
Lemma Let be the class of GCNNs defined in (5 with at most We parameters up layer l < L. and me GCNN units in layer É. For any integer m > 0, the growth function of this class can be bounded by
2emmmel
W,
20mL
Wx+1
Ty(m) S 2 II
We
WL +1
Proof. LemmaB5shove that after L layers, there are at most
L
(emrmel
We
2 Em1
II
We
regions in the parameter space W on which the GCNN units the last layer (1),)(9) 1 mL. f Fms g E Gr) behave like fixed polynomial function of degree S. L in W variables.
21

---

Recall that the final output of the neural network, is obtained by applying average pooling to the outputs of the GCNN units in the last layer. This implies that, for a fixed network architecture and input, the output of the neural network is a piecewise polynomial of degree at most I,, depending on all Wr network parameters. Since there are m possible inputs f1,..., Jm, we get m piecewise polynomials, each corresponding to one of these inputs. Bounding the growth function x (m) now means we need to count the number of different sign patterns that arises for classifiers in sign (H). For that, we recall that by Definition 3.2 in the main article,
sign (H) {sign(hw b)]lw E H.w ,, R).
Applying Lemma 4 to m polynomials of the form hw b of degree at most L and Wz + variables leads to no more than
2 W2+1
W (W++1
(30)
distinct sign patterns that the classifiers in sign(H) (H) can produce.
Thus, the growth function within each region, where the GCNN units in the last layer (hr,)(9) mL, g E G behave like fixed polynomial function in W variables, is bounded by (30).
As result, we conclude that the overall growth function (m) is bounded by
20mL
WL+1
L
2emrmal We
W.
2emL
WL+1
S(L) 2
24
II E=1
.2
WL +1
WT +1
This completes the proof.
For the proof of the Theorem we also use the following technical lemma
Lemma 7. Suppose 2
< 2 (miF)) for some 2 16 and m. i
2
0. Then m I
+ w (2 log r).
Proof of Theorem
Let VC(H). For convenience, define the sum
L
W
W
(31)
where W; denotes the number of parameters of GCNN in H up to layer
We consider two complementary cases and prove the theorem for each of them separately.
Case 1: m < W + WW + 1. In this case, we have W + W7 + < 3W < UBBH), where
(BH defined in 27 For the latter inequality we use that logz Ser El mi > Therefore, Theorem holds.
Case m 2 W + WT + Since m represents the VC dimension of H, follows from the definition of the VC dimension (see Definition 3.1 in the main article) that 11x (b([m) 2m Applying Lemma 6 gives us
L
2emrmel We
Wi (
(2emLL
WI+1
[1m) = 2 < 24+1
II t=1
(32)
WL +
Next, apply the weighted cüthmeticc-eomeetr mean (AM-GM) inequality the right side of (32), using weights We/(W Wr, + 1) for é 1,2,... L, and WL/(W + Wr, + 1), where W is defined in (31). This yields
W+W++1
n < 26-1 /2em(r E/e lmi + L)
W + +1
22

---

The last step of the proof involves applying Lemma 7 in 2 to this inequality, which provides an upper bound for m. Before doing so, we must verify that all conditions of the lemma are satisfied. In our case, mn corresponds to m, K to L + 1, v to W + WL + 1, and F to 2e(r Σi= bm + L). considering the case where
Since Σ/=1 mm + L 2, we have F 16. Morcover, m W + Wr. + 1, and it is straightforward to verify that W + Wz. + ++ 0. Therefore all conditions of Lemma] 7 in [2] are indeed satisfied and we obtain
< (L+1) 2W log2
(de(r)) t=1
4e
Eme + 1) log2
2e
Σ (=1
bme 11))
To simplify this inequality, we use that for all a 2 1, logz (2a log, a) loog (2a) + log, (log2 a) -
2 logg (2a). Substituting a 2e Eé= lime L) we note that S 4er Σi= lme and obtain
m S (L 1) 4W loga Ser Σ tme).
completing the proof of the theorem.
B Proof of Theorem 2
In this section, provide the detailed proof of lower bound on the VC dimension, along with the proofs for Lemmas 2 3 and their corresponding Corollaries and 3
The class
HW.L. (H(k, Tm, me, l&s L, W. WW},
(33)
includes all GCNN architectures with a total number of parameters bounded by W, maximum depth of I,, and r representing the cardinality of the discretized group G" == (21.02..... Or} containing the identity element e.
Next, we recall that F(mo...., m, represents the class of fully connected feedforward ReLU networks with L layers, where m, denotes the number of units in the i-th layer for i 1,...y L. The output of the last hidden layer of any neural network how E F(mo: -.000.....0... mz), with parameters w, can be written as vector of size m., that is, (T ,..,,,..,y, ((22))
Finally, we define the class
Fw. [F= me) les L, WI(F) WW)
(34)
consisting of DNNs with most T. hidden layers and a total number of weights not exceeding W. Lemma 8. Consider GCNNs where the G-correlation uses kernels from a one-dimensional vector space with fixed basis given by the indicator function of the identity element e. For every ha E F(mo.... ,..,,,,,,. there exists a GCNN bo with the same number of channels in each layer, i.e. hw H(1, (1, ..., mL, r), and parameters such that for any input.function function f G - 1R
mi
ΣΣ
()(()) hf)
Proof. Write H = H(1, mm......... mr, r). Consider fixed input function f G" + Rm and weight vector w E RW Recall that the number of parameters in a GCNN is given by
WL == Σ my(kmmm +1,
(35)
1=1
where & is the dimension of the kernel space. In our case and the number of parameters for GCNN with architecture H. is
W1
mf(mj-1 + 1).
(36)
23

---

This coincides with the number of parameters in DNN with architecture F(mo...... m.). Conse- quently, the same weight vector w E IR defines both, DNN function hww and GCNN function fw H when the input is fixed to f.
We now show that the outputs of the computational units in he and fow are equal when applied to fg) and g. respectively. Specifically, we aim to prove that
(f(g)) he,;(1));
where he, denotes a DNN computational unit in layer of hw. with parameters fixed to w, and he represents a GCNN computational unit layer É, with parameters fixed w and input set f. We prove this by induction on the layer f.
The statement holds trivially for the input layer, as (f = ho,)(g)) for any 95 E G". Assuming it holds for all layers up to é 1, now prove for layer l.
Let denote the indicator of the identity element e E G". By calculating the G-correlation between K and f. we obtain K * f f f. Combining this with the definition of the GCNN unit (see (9) in the main article) and the induction hypothesis, we have
124-1 Σ
he,) =
w 2,t h4 1,9)) (
(f-1) 1)
(8-1) 1) hh h11-10(99)) - -b(")
W
ii
(induction assumption)
(f-1) Wii K he he-1.) (gi) - -b!²)
(property of x)
Kw he-1,)) (g3) - b/:²)
(definition of learned kernel)
(93)
(definition of GCNN unit).
This shows that the outputs of the computational units in Ao and fw are equal when applied to f() and g. respectively.
Finally, the outputs of Tow = (TW ...,, (m(m)))) can be rewritten into the form
T0 (((r))) = hL =
hL,(00)) = 1o Iww())
j=1
concluding the proof of the lemma.
Next, we prove Lemma 2 The key ideas and steps of the proof have already been outlined in the main article, so here we will focus on the formal statements that still needs to established.
Recall that the indicator neural network
(a.b,e)
(37)
is a shallow ReLU network with four neurons in the hidden layer (see (25) in the main article). It
approximates the indicator function the interval (a, b] in the sense that (a.b.)) (x) 1 if (a, b). and 1 (z.))))(z)) = if <
I c.
Lemma 9. [Lemma P For I>> 3 let HoW.L+1,r be the class of GCNNs defined as in be the class of DNNS defined as in (34). Then
33 and FW.L.
VC(Hew.L415)) Z VC(Fw.L).
Proof. Let m be the VC dimension of the class of DNNs Fw,L. There are 2 possible binary classifications for set of m elements, subsequently denoted by d = 2m
By definition, there exists a natural number mo and a set of m vectors
y = {y )m} C. R
(38)
24

---

that can be shattered by subset of networks H. C. FW.L. Since there are more than d distinct classifiers for }/ the class H consists of most DNN functions.
Next, we construct DNN architecture using my + smaller DNN classes. One of these classes H. while the remaining classes consist of "indicator" networks, as described in (37). These indicator networks ensure that the combined DNN vanishes outside a certain my dimenssional hypercube. To define this hypercube, we use the set y from above.
Specifically, choose numbers A maxyey [y|l and B A, and define the mo-dimensional hypercube
{ ....... (ym A y B).
To construct a DNN that vanishes on IT, we define an approximate indicator function for II, using DNN with migdimmnsional input y (y1...... ymmo): ......
me
I m + R, I(y)
mo Σ
(AB.,,5))))
where ((A.B...))))) is indicator network that approximates the indicator function for values within B).
The final DNN is formed by combining functions from H with the indicator function I. Since DNNs can summed they have the same depth, we adjust the depth of to match the depth of the functions from H while ensuring that remains constant on ) and I1. Specifically, we use the fact (y) for the ReLU activation function o (xx) max(x, 0} (for any y from II or y). This means that by composing / with the required number ReLU functions, we can construct a DNN that satisfies the desired properties, This construction requires most L < W additional weights.
that for (y) > 0, a (I
To complete the proof, we need to show that there are m input functions Fm == ffi..... fm C {f: G + Rm that can be shattered by GCNNs from HoW,L+1,r- As the set Fm, we choose functions defined by fi(e) y: and [i( E TI for E G" and g # e.
By the definition of shattering (see definition in the main article), prove that Fn is shattered, it is sufficient to show that for any binary classifier C : Fm - {0, 1}. there exists a corresponding function in sign Ho.,, whose values coincide with those of on Fm.
Choose h H. such that for some e sign sign(h(y:) - b) C(fi) for i I,..., m.
Since II is compact, we define
T= max h(y)]- yen
The final DNN he adjusts such that it vanishes II but coincides with sign(h 6) on V.
he = [ (T bbT (0--) b).
with (z) = max( 0}
Thus, for any fi E Fms
sign(h(y)) -b) C((.). Σ ihe(kiail)) j=1
sign
By Lemma 8 we can define GCNN he such that he(f) E.= he (f(gg))) for any Fm. This implies that (fgn(he(f; b)) C(f+) for any fi E F...
As the number of weights in he is W + L + 4mg < 6W, this shows that our GCNN is in the class completing the proof of the lemma.
Corollary 4. [Corollary 2 In the setting of Lemma
2 if the number of layers L > and < W0.99
then there exists a constant e such that
VC(Hw.L,) 2 vV(Fw.L).
25

---

we know that for the class of fully connected neural networks Fw.,. with L layers and most W overall parameters, there exist constants co and Co such that
Proof. From Equation (2) in [3
W
Co W log
S vC(FF.L)) S Cu WL log W.
(39)
Moreover, by Lemma 9 we have
"C(HoW",L'4L) N VC(Fw).)).
By choosing W 6W and I. T'' + 1, this shows that
VC(Hw,L.F) 2 VC(FLLwJ,L-1).
To obtain the statement in the lemma, we combine this bound with the left inequality in 33 leading
VC(Hw,,.r)) 2 VC(F fwI.L-1) 2 ou (:
W -
(L - 1) log
L -
For some constant C₁ 0, the right-hand side of this inequality is bounded from below by
WL log W.
By using the right inequality in 33 this can further bounded,
C1 WL log W vC(Fw,L),
showing the assertion.
Next, provide the proof for the second part of Theorem 2 which states that for universal
constant e > 0, the VC dimension JC(Hw,L.r) ).) is bounded by c W (ogg(r). As mentioned in the main article, the first step of the proof is Lemma
Lemma 10. [Lemma 3/ Let HA, be the class of GCNNs defined in
33
Then
VC(HA.L.)) 2 [logar].
Moreover, for any numbers A B, there exists finite subclass of GCNNs H. C. H4,L, that shatters a set of [log2 r] input functions
Fm Ltf GT [] =1,,,... I,..., [loge r]}.
and outputs zero for any function f: G" +R [A,
Proof. To simplify the notation, m = logz rJ. It will be enough to show that a subelass of GCNNs H HA,L. shatters the set of m input functions as this immediately implies that
VC(H4,1.))) 2 [logar]] T--
The proof involves selecting d = 2 distinct points in the interval [A, B) and defining "indicator" neural networks of the form (37) that output at exactly one of these points. By adjusting the parameters of these networks, we can control the intervals of our indicator networks and ensure that each network outputs the desired point.
Specifically, define = B-A and select the d points
2[
y = {ı A + 18 i=
The input functions F., are now chosen from { GT (B
There are d 2 different binary classifiers for the set of elements. Each binary classifier is defined by the elements for which outputs 1, and we can index these classifiers by the subsets of 21,2, ... m). denoted by S Sg. In our construction, each y, y corresponds to the binary classifier determined by 5,. More formally, the set of m input functions F.. == {fi,..., fm is defined by
$ Vi.
if St, otherwise.
88-8
26

---

Hw HAW.L, shatters the set Next, we define the finite subclass in Ha,,,r that shatters Fm and outputs zero for any function f: G" - B).
By the definition of shattering (definition in the main article), for any binary classifier C Fm {-1,1), need to find function in sign(Hs,1.r)) matching C on F.n-
For any classifier C Fm + {-1,1} we can find subset 5 S {L...., m) such that C(f) 1f j E S and C(f)) = -1 -f E S There exists index i" such that S = S Using Lemma 8 one
can construct a GCNN h1g- E Ha,L,r that matches C on Fm. Indeed, for any fz Fm.
f1, (0, otherwise.
if
bo hzz(
Σ - i +2 22 (1
(40)
Thus, sign(h.. (f) - 0.5) C(f) for all f E Fm- As an 'indicator' neural network 1 (2)- 2.0e + +9.4)
has only 4 parameters and 2 layers, it is in H..L.r.
Morcover, for any i ...... d and any z R [), 1 ( -0--4m 4 = 0. Arguing as for (40)
h (/-( = for any f G" + \A, B).
That means that the class H. == (hi,..., ha} shatters input functions Fm and outputs 0 on the subset {f G + R [A,
B]}. This completes the proof.
Corollary 5. [Corollary By The VC dimension of the class HaW.L. consisting of GCNNs with 4W weights, L layers, and resolution satisfies the inequality
VC (HAW,L,)) 2 W [logg rJ.
Proof. To simplify notation, let m == [log2 r..
We prove this corollary by defining W disjoint intervals [A1, Bı).-... [Aw, Bw], where A, (m + 3) and B; = (m + 2).. For different i E {I...., W the set of input functions Fi = {
G" + [A; B:]} is disjoint since the values of the intervals do not overlap.
By Lemma TO for each 1,.... W, we can find a class of GCNNs H, C Ha.L.r that shatters set of input functions Fm, C J, and outputs 0 on any other set Fm.j, where #
Next we show that the class of GCNNs H = H4 + H2 Fm = -.!! Fm,.. This will prove the corollary. By the definition of shattering, need to find for any binary classifier C: Fwm. + {0, 1), function in sign (Pt that matches C on Fwm-
For = 1...., W, let C, = C [mn.. be the restriction of C to Fm,.. As Hi shatters Fm,i. we can choose a GCNN he, E H. such that its values match those of C, on Fm,..
Next, we show that the values of the GCNN he = Ew he, match on Fwm- Let f be any input function from m. say f E Fq. For any & q. it holds that (f, O since he, E H4. Thus,
w
Σ
he, he) = (f).
Since hf) =(f)) by the choice of he,- it follows that lc(l)) C(f) for any f E Fwm. This shows that the class H of GCNNs shatters Fwm. proving the corollary.
C On the constants in Equation
While our main focus is on the asymptotic behavior of the VC dimension, it is instructive to express the constants and for GCNNs terms of the corresponding constants for DNNs. For DNNs, the Eq(2) from 3 states that there exist universal constants cy and Cy such that
W
CF WLLog
< VC(Fw.))
max UB(F) < Cr WL log W. FEFW.
(41)
L
27

---

where (B) denotes an upper bound on the VC dimension for the class F. As we show now, under the commonly satisfied assumptions that W L and W 125, we obtain
CF 0.04, CF = 5, c 7500*
C 500.
To derive an explicit lower bound for the constant OF for the class F of DNNs with most W weights and L layers, we follow Theorem 9 [3]. This theorem constructs networks with VC dimension 2 mn, where the architecture has 5k layers,
2 n + 4m + k ((11 + r)2" + + 2) network parameters,
input nodes, and
m + 2 15 2" +r+1)
computational nodes. For the parameter choices
loge T
W
rL
m
n W 5m 2
the VC dimension satisfies
rL (W 5m 2")
W L logg ( (
logg W
L
VC(F) N mn
V
8
16
16
W
To refine the estimate further, we use the assumption that W > L and W >> 125, such that
WLg
W
5 5lgg (1 WW)
VC(F)
16
16
W1/4
W loga
0.674 > 0.04W loga
16
L
That means that cy be chosen 0.04.
To derive an explicit value for Cz. follow the proof of Theorem from 3 In that proof, is stated that:
VCdim L+
W loga (4epRlog,
where
R W + W(L 1)db-1 In the case the ReLU activation function, we have = = and so,
VCdim F) I
Σw, W.
Σ
logz (4epR (2)p()))
< L + 2WL Log, (4epR)
< + 2W L log, (4eW)) L)
$ + 2W L log, (/e33/22
< 3W logz (4eW)
Under the assumption that W 2 and 125, we have
L + W logg(4e) < L 1.5W log, (125) < L + 1.5W L (o), < 2W Log,
leading
VCdim < 5WL (W),
and Cf 5. Therefore - 125.
To derive and c, recall that
CF W WoLlogWW/1) VC(Fw.L) S SUB(FW.)) S CF W W W.
(2)
28

---

Imposing again the assumptions that W > L and W > 125, we have
CF 2 B.C7 250VC(Fw..).
UB((W.L)) - OF
Using this and Eq. 19 we obtain
VC(Hw,L.) & 2U SW L logr & 500(VC(Fw,,) + WL Logr).
For the lower bound, using Lemma
we estimate
W
W log
C L log W
5
5(L - 1)
1 OF -VC(Fw.))
VC(Fw,1)
60
Cf
7500
Under stronger assumptions (e.g., W 2 Lº), tighter bounds can be derived.
29


Reviews:
[{"review_id": "y3ScmEZLzW", "reviewer": "Reviewer_6nZ2", "summary": "The paper gives generalization bounds for certain Group Convolutional Neural Networks (GCNN), in particular cases in which the group is finite or which use a discretization by finitely many points of a (compact Lie) group. They have upper and lower bounds of VC dimension of GCNNs through the VC dimension of standard NNs with the same number of layers and weights per layer. The bounds involve a term in log(r) where r is the cardinality of the group. A special case is that of convolutional neural networks.", "questions": "I have just somehow minor questions.\n\n1) What are the constants from equation (1)?\n\n2) A curiosity: Does the approach give similar bounds on fat-shattering dimension?\n\n3) Line 73: \"groups such as rotations or translations are often discretized\": then if the approximation of a Lie group is by a number of elements r that tends to infinity, will the bound (1) give infinite VC dimension as r tends to infinity? Or what is the version of the result for continuous compact Lie groups?\n\n4) line 284 : \"lemma 17\" does not appear anywhere, what's the correct number?", "limitations": "I don't think \"societal impact\" applies to this kind of result.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: This is a new result on GCNN generalization bounds.\n\nStrength: The result has upper and lower bounds, with equal growth behavior.\n\nWeakness: The results only concern finite groups, and only describes VC and pseudodimension.\n\nOverall I think that the strengths override the weaknesses. The result is interesting but I wouldn't go above \"borderline accept\" due to the weaknesses.", "was_revised": true, "final_justification": "After discussion with the authors, I consider that my assessment did not change considerably.", "rebuttal": "We are very grateful for the time and effort spent on our submission. Please find a detailed point-by-point response below. \n\n**1. What are the constants from Equation (1)?**\n\nOur main focus is on asymptotic bounds. To obtain explicit expressions for the constants $c, C,$ it is necessary to carefully follow the proof steps. This also requires making the constants in Bartlett et al. (2019), _Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks_ explicit. Let $c_{\\mathcal{F}}$ and $C_{\\mathcal{F}}$ denote the constants appearing in their VC dimension bounds for standard fully connected networks.\n\nUnder the commonly satisfied assumptions that $W > L^2$ and $W > 125$, we obtain\n$$c = \\frac{1}{120} \\cdot \\frac{c_{\\mathcal{F}}}{C_{\\mathcal{F}}}, \\quad C = 4 \\cdot \\frac{C_{\\mathcal{F}}}{c_{\\mathcal{F}}}.$$\nFollowing the bounds in Bartlett et al. (2019), we can derive $c_{\\mathcal{F}} = 0.04$ and $C_{\\mathcal{F}} = 5.$ Substituting these values yields:\n\n$$c = 0.00006, \\quad C = 500.$$\n\nA detailed derivation of these constants and their dependence on $c_\\mathcal{F}$ and $C_\\mathcal{F}$ will be included in the appendix of the final version.\n\n**2. A curiosity: Does the approach give similar bounds on the fat-shattering dimension?**\n\nYes — for ReLU networks, the fat-shattering dimension and the pseudodimension coincide up to constant factors. This is because the ReLU activation is positively homogeneous: scaling the output of the last layer by a positive constant scales the whole network output.  Since $\\mathcal{H}_{W,L,r}$ is closed under multiplication by positive scalars, the fat-shattering dimension coincides with the pseudodimension (see Theorem 11.14 in Anthony and Bartlett (1999)). Hence, our upper and lower bounds remain the same.\n\n**3. Line 73: What happens as $r \\to \\infty$ (or for continuous Lie groups)?**\n\nYes, your interpretation is correct. If the group approximation becomes arbitrarily infinite (i.e., $r \\to \\infty$), and no regularity assumptions are made on the input data (e.g., continuity or smoothness with respect to the group action), then the VC dimension diverges to infinity. This also holds for continuous compact Lie groups. A discussion of this phenomenon appears also in Petersen et al.  (2024), _VC dimensions of group convolutional neural networks_ .\n\n**4. Line 284: ``Lemma 17'' does not appear anywhere — what's the correct number?**\n\nThank you for catching this typo. The correct reference is **Lemma 8.** We will fix this in the revised version."}, {"review_id": "wtWL1IpD9N", "reviewer": "Reviewer_qLBm", "summary": "This paper gives mathematical upper and lower bounds on the Vapnik-Chervonenkis (VC) dimension of deep Group Convolutional Neural Networks (GCNNs) with ReLU activations. The authors show that the VC dimension grows with the number of layers L, the total number of learnable weights W, and logarithmically with the size |G| of the discretized group that acts on the inputs. The bounds are almost tight and extend earlier work, which covered only two-layer GCNNs or continuous groups, to deeper architectures and practical finite groups. They also compare their results with known VC bounds for ordinary deep feed-forward networks and discuss sample-complexity consequences.", "questions": "1. How would your bounds will change if you choose other activations, for example, leaky-ReLU or smooth activations?\n2. Have you estimated the inexplicit constants in the bounds to give practitioners guidance on required sample sizes?\n3. Do the results extend to equivariant GCNNs that end with global max pooling instead of average pooling?\n4. Could the logarithmic term in log |G| be improved if the group has additional structure (e.g., Abelian)?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\nThe main value of this paper is the theoretical aspects.  It gives the first almost-tight upper and lower bounds on the VC dimension of deep  GCNN built on a finite group (or discretized elements of continuous group).  The authors prove that the VC dimension rises linearly with the number of layers and weights, but only logarithmically with the size of the group, using the method of the polynomial partitioning.  This extends older results that covered only shallow networks. By writing their bounds as *VC dimension of a standard deep network + $W \\log |G|$\", they show clearly that adding  symmetry costs very little in a sample complexity.  \n\n## Weakness\nThe scope of this paper is relatively narrow:  all proofs assume that the activation is ReLU, and other activations remain open questions.  The work is purely theoretical, namely, there are no experiments or simulations to check how large the hidden constants are, so readers  cannot tell how many samples they really needs in practice.  While the bounds provides a hint that increasing the group resolution does not affect the size of VC dimension so much, the paper offers little practical advice on how to choose the resolution of the group and the number of weights.", "was_revised": true, "final_justification": "Rebuttal convincingly covers leaky-ReLU and global max pooling; the lower-bound tweaks are sound. Still open: smooth activations (esp. upper bounds), constants not fully integrated, and no empirical checks. The novelty and near-tight theory for deep GCNNs outweigh these practicality gaps—hence borderline accept.", "rebuttal": "Thank you for your feedback. It is very helpful to further improve this submission. \n\n**How would your bounds change if you used other activations, such as leaky-ReLU or smooth activations?**\n\nThe bounds remain the same for leaky-ReLU, as is the case for standard deep neural networks. The upper bound holds because leaky-ReLU is also a piecewise linear function with two linear segments, similar to ReLU. Thus, all arguments used in the proof of the upper bound apply directly.\n\nTo justify that the lower bound still holds, we outline the necessary modifications to Lemma 2 and 3. We replace the indicator function by\n$$ \\tilde{I}\\_{A,B}(x) := \\frac{1}{\\epsilon} \\Big[(x-(A-\\epsilon))\\_{+,\\alpha} - (x-A)\\_{+,\\alpha} -  \n\\big((x-(B-\\epsilon))\\_{+,\\alpha} - (x-B)\\_{+,\\alpha}\\big)\\Big], $$\n\nwhere $(x)_{+,\\alpha} := \\max(x,\\alpha x)$, $0<\\alpha<1$ is the Leaky ReLU parameter, $\\epsilon > 0$, and $A < B-\\epsilon$. This function is zero outside the interval $[A-\\epsilon, B]$, and equal to 1 inside $[A, B-\\epsilon]$.\n\nFor Lemma 2, we use a fully connected network with leaky-ReLU activations. In our construction, we used a DNN that outputs zero for inputs outside a predefined hypercube and outputs a value $>1$ for inputs inside a smaller subcube. This property still holds for leaky ReLU activation.\n\nSpecifically, we redefine the final function in Lemma 2 as:\n$$\\tilde{h}\\_{\\mathcal{C}} \\coloneqq \\mathrm{LeakyReLU}\\big( \\tilde{h} - (T - b)\\tilde{I}\\_{A,B} - b \\big) $$\n\nand select $f \\in F_m$ such that $f(g) \\in \\Pi := {\\mathbf{y} \\in \\mathbb{R}^{m_0} : A \\leq y_i \\leq B -\\epsilon }.$\n\nIn Lemma 3, we used the following construction: select $d = 2^m$ distinct points in $[A, B]$, and design networks that output 1 at exactly one point each. The use of $\\tilde{I}_{A,B}$ remains valid if we choose the points in $[A, B-\\epsilon]$ instead of $[A, B]$.\n\nFor general smooth activation functions, the current proof strategy does not extend directly. While a lower bounds appears feasible due to the ability of sigmoidal networks to approximate the indicator function \n\\begin{align*}\n    \\sigma(k\\cdot (x-A))-\\sigma(k(x-B)) \\approx \\mathbf{1}_{[A,B]}(x), \\quad \\text{as} \\ k \\to \\infty, \n\\end{align*}\none must carefully account for the fact that the network only approximates the binary outputs 0 and 1. \nIn contrast, the upper bound does not follow readily. The region-counting argument, which applies to networks with piecewise polynomial activations like ReLU, breaks down for sigmoidal networks due to the absence of polyhedral decision boundaries. While alternative techniques have been used for sigmoid-activated networks, such as bounding the number of sign configurations of compositions of sigmoids and affine functions, these strategies do not directly extend to GCNNs and would require significant adaptation. Moreover, as noted by Bartlett and Anthony  (1999, Chapter 8), existing VC dimension bounds for deep neural networks with sigmoidal activations exhibit a substantial gap between known upper and lower bounds, indicating that even for vanilla DNNs the current results are not tight.\n\n**Have you estimated the constants in the bounds to help practitioners estimate required sample sizes?**\n\nWe provided estimated constants in our response to Reviewer 6nZ2. \n \nIn practice, the VC dimension relates to generalization through the fundamental theorem of learning theory, stating that\n$$m = O\\left( \\frac{\\mathrm{VCdim}(\\mathcal{H}) + \\log(1/\\delta)}{\\varepsilon^2} \\right),\n$$\nwhere $m$ is the required number of training samples to guarantee that the empirical loss approximates the true loss within $\\varepsilon$ with probability at least $1 - \\delta$. Thus, bounds on the VC dimension directly reveal the influence of the architecture on the learning complexity. \n\n**Do your results extend to equivariant GCNNs that end with global max pooling instead of average pooling?**\n\nYes, the results still hold for global max pooling.\n\nFor the lower bound, note that in Lemmas 2 and 3, the constructed examples have nonzero values only at a single group element. In such cases, global max and average pooling produce identical results, so the lower bound is preserved.\n\nThank you for pointing this out. We will include in the revised version. \n\n**Could the logarithmic term in $\\log |G|$ be improved if the group has additional structure (e.g., is Abelian)?**\n\nOur results hold for any finite group $G$, regardless of its algebraic structure. We make no assumptions beyond finiteness."}, {"review_id": "pPdwjWwXAa", "reviewer": "Reviewer_4cFh", "summary": "This paper provides upper and lower bounds for the VC dimension of group CNN (GNNs) showing that for finite groups that the VC dimension of a GCNN is roughly equivalent to that of an unstructured DNN with the same number of parameters / layers. It builds on existing work by showing considering networks of arbitrary depth.\n\nDespite my concern about whether or not the VC dimension is the right tool to analyze equivariant ML, I still think this paper makes a major advance in our understanding. (Indeed this analysis is what motivates me to suggest we need a new notion of VC dimension in the comments below.) Overall, I think this is a good paper.\n\nNote: My score is conditioned on the authors making all of the requested edits and I reserve the right to change it if they do not.", "questions": "Do we require G^r to be a subset of G?\n\nWhy isn't the definition of \\mathcal{K}\\ast f normalized in equation (5)\n\nWhere does the formula (16) come from?\n\nIn the proof of Lemma 1, where does the identity VC(F_r) \\approx W(F_r)L log(W(F_r)) come from?\n\nIn the proof of Lemma 5, where does the \"at most m_{ell+1}mr\" polynomials come from?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nVC dimension has traditionally played an important role in understanding model generalization. This work extends this to GCNNs thus increasing the theoretical foundations of geometric deep learning\n\nThe paper is generally well written and explained\n\nProofs are well organized and appear to be correct. Morever, the analysis is highly nontrivial. (I do admit that as someone who only has a cursory understanding of the VC dimension that I was not able to understand every step in its entirety.) \n\nWeaknesses\n\nIt would be helpful to have a survey of a) why we care about the VC dimension, e.g., recalling the generalization bounds of ML algorithms that depend on it and b) what results are known for various DNN models, possibly in the appendix. This would help keep the paper self-contained for the reader.\n\nI think the claim that K\\ast g = r \\cdot K \\star g is an approximation not an equality. If not, please justify. (Maybe it is true in expectation if the elements of G^r are sampled randomly from the Haar measure?)\n\nComment: \n\nI am a bit unsure if the VC dimension is the \"right\" way to understand the advantages of equivariant ML.  It essentially analyzes the ability to learn arbitrary functions on SOME data set with a given cardinality. In some sense, it is not surprising that the VC dimension would then be the same for equivariant / non-equivariant models. To me, it seems that the advantages of equivariant ML is that it restricts the model class to not be able to express functions with the wrong symmetries. Therefore, it seems that equivariant / non-equivariant methods should be able to express arbitrary functions on data sets of the same size as long as the data sets didn't include two points from the same orbit of the group action. \n\n(continued) It might be better to have some notion of an \"equivariant VC dimension\" which analyzed the ability of a GCNN to shatter data in terms of the number of orbits present. Here, the ability of a DNN to express arbitrary functions would be only in terms of the number of distinct points, but the GCNN would be forced to be constant on orbits. In this manner the GCNN and DNN would have the same \"standard\" VC dimension but the GCNN would have a lower equivariant VC Dimension if the data had many \"repeat data points\" from the same orbit\n\nMinor:\n\nIn the definition of a group, there is a \"for all\" missing in the definition of the inverse.\n\nLine 207: proof sketch is in Section 5, not section 2\n\nMore detail should be given in the final inequality of Lemma 1. Also, the O should be a Theta \n\nThe m in the p_m(x) in Lemma 4 is missing a tilde\n\nTitle of Appendix A/B, theorem should be capitalized", "was_revised": true, "final_justification": "I stand by my initial review and think this is a good paper", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback. We believe that these suggestions have improved the clarity and rigor of our work, and we look forward to incorporating them into the final version.\n\n- **Consider including a brief survey of: (a) why VC dimension matters, e.g., in generalization bounds; and (b) existing VC results for DNNs.**\n\n    Thank you for this suggestion. We agree that this addition would make the paper more accessible, especially for readers unfamiliar with the role of VC dimension in learning theory. We will include a brief overview and relevant references in the final version.\n\n    The main motivation for studying VC dimension is its role in generalization guarantees, as explained to Reviewer qLBm. Moreover, there is a close relation between the VC dimension bounds and the expressive power of neural networks. In particular, upper bounds on the VC dimension directly imply lower bounds on feasible approximation rates. Most of the known VC dimension bounds for DNNs are summarized in Anthony and Bartlett (1999). In Bartlett et al. (2019) tightness of VC dimension bounds for piecewise linear activation functions is shown. We will include a summary of known results in the revised version. \n\n- **It might be better to define an \"equivariant VC dimension\" based on the number of orbits in the data.**\n\n    Thank you for this insightful comment. It would indeed be valuable to define an \"equivariant VC dimension\" that accounts for the model's constraint to produce outputs that are constant on orbits. This could reflect more realistic limitations of GCNNs when data points are repeated across orbits.\n\n    Our paper focuses on the standard VC dimension. In this sense, GCNNs and DNNs have the same capacity when data lies on distinct orbits. However, under more structured data assumptions (e.g., repeated or orbit-related data), an equivariant VC dimension may better capture model expressivity. This is a promising direction for future work.\n\n- **Clarify the claim that $K \\ast g = r \\cdot K \\star g$. Is this an approximation?**\n\n    This is indeed an equality under our definition of $\\star$. Please refer to Equations (4) and (5) in the paper. We agree that this notation may be confusing, but using $\\star$ helps to streamline technical proofs.\n\n- **Do we require $G^r \\subseteq G$?**\n\n    Yes, we assume that $G^r \\subseteq G$, as our convolutional filters are defined over $G$.\n\n- **Why isn't the definition of $\\mathcal{K} \\ast f$ normalized in Equation (5)?**\n\n    We dont have the normalization factor in Equation (5) to simplify the technical proofs. This simplification helps in the proofs of Lemmas 8--10 (Lemmas 2--3 in the main text).\n\n\n- **Where does Equation (16) come from?**\n\n    Equation (16) is derived by counting the total number of weights in the network. For each layer $j$, every computational unit computes an affine function over the outputs of the previous layer using $k$ kernel basis functions. This means that each unit in layer $j$ has $k m\\_{j-1}$ weights (one for each combination of a kernel and a unit in layer $j - 1$), plus one bias term. Therefore, each unit contributes $k m\\_{j-1} + 1$ weights, and with $m\\_j$ units in layer $j$, the total number of weights between layers $j - 1$ and $j$ is $m_j (k m\\_{j-1} + 1)$. Summing over all layers yields the total number of weights in the network, as derived in Equation (16).\n\n- **In the proof of Lemma 1, where does the identity $VC(F_r) \\approx W(F_r) L \\log W(F_r)$ come from?**\n\n    This follows from Bartlett et al. (2019), specifically Equation (2) and its corollary, under the assumption that $W^{0.99} > L$.\n\n- **In the proof of Lemma 5, where does the ``at most $m_{\\ell+1} m r$'' polynomials come from?**\n\n    We are counting polynomials in the parameters of the neural network. To do so, we fix a computational unit in layer $\\ell + 1$, a group element $g \\in G^r$, and an input function $f \\in F_m$. For each such triple, we obtain at most one distinct polynomial. Therefore, the total number of such polynomials is at most the product of the number of units in layer $\\ell + 1$, the number of input functions in $F_m$, and the number of group elements in $G^r$, resulting in at most $m_{\\ell+1} m r$ polynomials."}, {"review_id": "lMSPVCEA8e", "reviewer": "Reviewer_29km", "summary": "This paper studies the generalization capacity of group convolutional neural networks. It identifies an insightful relationship between the VC dimension of a set of fully connected neural networks and group convolutional neural networks (Equation 1). \nIntriguingly, the GCNNs have a larger VC dimension than their fully connected counterparts, even if the same number of parameters are assumed. This sheds light on the effectiveness of CNNs and corresponds well to empirical observations.", "questions": "I do not have any questions. I feel like I have fully understood the manuscript. The authors could only increase my score by picking a significantly harder problem and solve that.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think the writing is clear, and the mathematical arguments are sound. The manuscript is very focused on the main point---the VC dimension bounds described in Equation 1. The title, abstract, and introduction all appropriately describe the results, without oversimplification or exaggeration. \n\nThe only weakness is that, while the results are interesting, I would not describe them as ground-breaking. Still, this is a very good paper.", "was_revised": true, "final_justification": "It seems that the authors agree with my initial report.", "rebuttal": ""}]

Author rebuttal:

Meta-review: The paper establishes nearly tight upper and lower bounds for the VC dimension of deep group convolutional neural networks (GCNNs) with ReLU activations, showing that their growth matches that of standard deep networks in terms of layers and weights, with only a logarithmic dependence on the group size. This result extends prior work on shallow or continuous-group networks, offering the first general treatment for deep architectures on finite or discretized groups. Strengths include the novelty of the contribution, the clarity and rigor of the proofs, and the fact that the results capture both upper and lower bounds with matching growth, thereby solidifying the theoretical foundations of geometric deep learning. Reviewers appreciated the writing, the nontrivial analysis, and the insight that group symmetries increase sample complexity only marginally. Weaknesses noted include the narrow scope (results apply only to finite or discretized groups, with ReLU activations, and only in terms of VC and pseudo-dimensions), the lack of experimental validation or discussion of hidden constants (leaving practical implications unclear), and the limited broader impact since VC dimension may not fully capture the advantages of equivariant learning. Some reviewers suggested extensions (such as fat-shattering dimension, other activations, different pooling choices, and structured groups (e.g., Abelian) ) and one reviewer raised the need for an “equivariant VC dimension” that accounts for orbit structure (a related notion is discussed in this paper by Farrell et al. arxiv: 2110.07472 -- although not directly applicable to the problem here). Minor issues were noted in definitions, references, and clarity of certain proofs. Overall, the paper is well written, mathematically sound, and makes a meaningful though not ground-breaking advance; reviewers converge around a borderline-accept to accept recommendation.

Overall, I concur with the reviewers that the paper makes a good step in the theoretical picture around GCNNs, and would lean towards acceptance.
Decision: Accept (poster)