Approximation-Generalization Trade-offs under (Approximate) Group Equivariance
Authors: Mircea Petrache
Shubhendu Trivedi
Venue: NeurIPS 2023 poster (2023)
Keywords: Equivariance
Invariance
Generalization
Equivariant Neural Networks
Approximation Error
TL;DR: We prove results that tease out conditions under which the model symmetry is optimal for a given data symmetry in (approximate) group equivariant machine learning methods..

Abstract: The explicit incorporation of task-specific inductive biases through symmetry has emerged as a general design precept in the development of high-performance machine learning models. For example, group equivariant neural networks have demonstrated impressive performance across various domains and applications such as protein and drug design. A prevalent intuition about such models is that the integration of relevant symmetry results in enhanced generalization. Moreover, it is posited that when the data and/or the model exhibits only approximate or partial symmetry, the optimal or best-performing model is one where the model symmetry aligns with the data symmetry. In this paper, we conduct a formal unified investigation of these intuitions. To begin, we present quantitative bounds that demonstrate how models capturing task-specific symmetries lead to improved generalization. Utilizing this quantification, we examine the more general question of dealing with approximate/partial symmetries. We establish, for a given symmetry group, a quantitative comparison between the approximate equivariance of the model and that of the data distribution, precisely connecting model equivariance error and data equivariance error. Our result delineates the conditions under which the model equivariance error is optimal, thereby yielding the best-performing model for the given task and data.

Approximation-GGnerlllttttoo Trade-offs under (Approximate) Group Equivariance
Mircea Petrache"
Shubhendu Trivedi"
Abstract
The explicit incorporation of task-specific inductive biases through sym- metry has emerged as a general design procept in the development high-performance machine learning models. For example, group equivariant neural networks have demonstrated impressive performance across various domains and applications such protcin and drug design. A prevalent intuition about such models is that the integration of relevant symmetry results in enhanced generalization. Moreover, is posited that when the data and/or the model may only exhibit approzimale or partial symmelry, the optimal or best-performing model is one where the model symmetry aligns with the data symmetry. In this paper, we conduct formal unified investigation of these intuitions. To begin, we present general quantitative bounds that demonstrate how models capturing task-specific symmetries lead to improved gencralization. In fact, our results do not require the trans- formations to be finite or even form a group and can work with partial or approximate equivariance. Utilizing this quantification, we examine the more general question of model mis-specification i.e. when the model symmetries don't align with the data symmetries.. We establish, for given symmetry group, quantitative comparison between the approximate/ partiaa partial equivari- ance of the model and that of the data distribution, precisely connecting model equivariance error and data equivariance error. Our result delineates conditions under which the model equivariance error is optimal, thereby yiclding the best-performing model for the given task and data. Our results are the most general results their type in the literature.
Introduction
It is common intuition that machine learning models that explicitly incorporate task-specific symmetrics tend to exhibit superior generalization. The rationale is simple: if aspocts of the task remain unchanged or change predictably when subject to certain transformations, then, a model without knowledge of them would require additional training samples to learn to disregard them. While the general idea is by no means new in machine learning, it has experienced a revival interest due the remarkable successes of group equivariant convolutional neural networks (GCNNs) [14, 38, 29, 16, 13, 60, 8, 34, 24, 66). Such networks hard-code equivariance to the action an algebraic group on the inputs and have shown promise in variety of domains [55, 5, 42, 2, 28, 62, 25, 52, 18, 61, 68), in particular in those where data scarce, but exhibits clear symmetries. Further, the benefits of encoding symmetries in this manner extend beyond merely enhancing generalization. Indced, in
"UC Chile, Fac. de Matemáticas, & Inst. de Ingeniería Matematica Computacional, Av. Vicuña. Mackenna 4860, Santiago, 6904441, Chile. mpetrachedmat. cl. shubhendu@csail mit.edu.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

numerous applications in the physical sciences, neglecting to do so could lead to models producing unphysical outputs. However, the primary focus of most of the work in the area has been on estimating functions that are striclly equivariant under a group action. It has often been noted that this may impose an overly stringent constraint as real-world data seldom exhibits perfect symmetry. The focus on strict equivariance is partly due to convenience: the well-developed machinery of group representation theory and non- commutative harmonic analysis can easily be marshalled to design models that are exactly equivariant. A general prescriptive theory for such models also exists [29, 16]. In a certain sense, the basic architectural considerations of such models are fully characterized.
Recent research has begun explore models that enforce only partial or approximate equivariance [40, 59, 23, 56]. Some of these works suggest interpolating between models that are exactly equivariant and those that are fully flexible, depending on the task and data. The motivation here is analogous to what we stated at the onset. If the data has a certain symmetry whether exact, approximate or partial and the model's symmetry does not match with it, its performance will suffer. We would expect that model will perform best when its symmetry is correctly specified, that is, it aligus with the data symmetry.
Despite increased research interest in the area, the theoretical understanding of these intu- itions remains unsatisfactory. Some recent work has started to study improved generalization for exactly equivariant/ intivariant/ivvaiian /invariant models (see section 2). However, for the more general case when the data and/or model symmetries are only approximate or partial, a general treatment is completely missing. In this paper, we take a step towards addressing this gap. First, we show that a model enforcing task-specific invariance/ /equivvaaaiiivvaaaaeee exhibits better generalization. Our thcoretical results subsume many existing results of a similar nature. Then we consider the question of model mus-specification under partial/apprxximate symmetries of the model and the data and prove general result that formalizes and validates the intuition we articulated above.
We summarize below the main contributions of the paper:
We present quantitative bounds, the most general to date, showing that machine learning models enforcing task-pertinent symmetries in an equivariant manner afford better generalization. In fact, our results do not require the set of transformations to be finite or even be a group. While our investigation was initially motivated by GCNNs, our results are not specific to them.
Using the above quantification, we examine the more general setting when the data and/or model symmetrics are approrimate or partial and the model might be misspecified relative to the data symmetry. We rigorously formulate the relationship between model equivariance error and data cquivariance error, tcasing out the procise conditions when the model equivariance error is optimal, that is, provides the best generalization for given data. To the best of our knowledge, this is the most general result of its type in the literature.
Related Work
As noted earlier, the use of symmetry to encode inductive biases is not a new idea in machine learning and is not particular to neural networks. One of the earliest, explorations of this idea in the context of neural networks appears to be [46]. Interestingly, [46] originated in response to the group invariance theorems in Minsky & Papert's Perceptrons [36], and was the first paper in what later became research program carried out by Shawe-Taylor & Wood, building more general symmetries into neural networks [63, 48, 49, 65, 64], which also included PAC style analysis [50]. While Shawe-Taylor & Wood came from a different perspective and alrcady covered discrcte groups [14, 38), modern GCNNs go beyond their work [29, 16, 13, 60, 8, 34, 24]. Besides, GCNNs [14] were originally proposed as generalizing the idea of the classical convolutional network [32], and seem to have been inspired by symmetry considerations from physics [15]. Outside neural networks, invariant/ /equuivariani methods have also been proposed in the context support vector machines [43, 57], general kernel methods [39, 26), and polynomial based feature spaces [44].
2

---

On the theoretical side, the assertion that invariances enhance generalization can be found in many works, going back to [47]. It was argued by [1] that restricting a classifier be invariant can not increase its VC dimension. Other examples include [3, 4, 51, 41]. The argument in these, particularly [51, 41] first characterizes the input space and then proceeds to demonstrate that certain data transformations shrink the input space for invariant models, simplifying the input and improving generalization. Some of our results generalize their results to the equivariant case and for more general transformations.
Taking a somewhat different tack, [22] showed a strict generalization benefit for equivariant linear models, showing that the generalization gap between least squares model and its equivariant counterpart depends on the dimension of the space of anti-symmetric linear maps, This result was adapted to the kernel setting in [19]. [9] studied sample complexity benefits of invariance in kernel ridge regression setting under a geometric stability assumption, and briefly discussed going beyond group equivariance. [53] expands upon [9] by characterizing minimax optimal rates for the convergence of population risk similar setting when the data resides on certain manifolds. [35] characterizes the benefits of invariance in overparameterized linear models, working with invariant random features projected onto high-dimensional polynomials. Benefits of related notions like data augmentation and invariant averaging are formally shown in [33, 12]. Using a standard method from the PAC-Bayesian literature [37] and working on the intertwiner space, [7] provide PAC-Bayesian bound for equivariant neural networks. Some improved generalization bounds for transformationninnaaae
functions
are proposed in [67], using the notion of an induced covering number. A work somewhat closer to some of our contributions in this paper is [20], which gives PAC bounds for (exact) group equivariant models. However, we note that the proof of the main theorem in [20] has an error (sce the Appendix for a discussion), although the error seems to be corrected the author's dissertation [21]. An analysis that somewhat overlaps [20], but goes beyond simply providing worst-case bounds was carried out by [45].
Finally, recent empirical work on approximate and partial equivariance includes [40, 59, 23, 56]. These make the case that enforcing strict equivariance, if misspecified, can harm performance, arguing for more flexible models that can learn the suitable degree of equivariance from data. However, there is no theoretical work that formalizes the underlying intuition.
Preliminaries
In this section, we introduce basic notation and formalize some key notions that will be crucial to ground the rest of our exposition.
3.1 Learning with equivariant models
Learning problem. To begin, we first describe the general learning problem which we adapt to the equivariant case. Let's say we have an input space X' and an output space } and assume that the pairs = (X, Y) X x y are random variables having distribution D. Suppose we observe sequence of n i.i.d pairs Z, = (X,, Y.) D, and want to learn function f X + y that predicts Y given some X. We will consider that f belongs to class of functions F C (f: X + }}} and that
work with a loss function é X x y + [0, co). To fully specify the learning problem we also need a loss class, comprising of the functions f(x, v) = (((())) v) X + [0, 20). Using these notions, we define:
F= (((x = ((((), JEJ,, Pf: Pf=
Paf: -
1=1
The quantities Pf and Paf are known as the risk and the empirical risk associated with f. respectively. In practice we have access to P.f, and we estimate Pf by it. One of the chief quantities of interest in such a setup is the worst-case error of this approximation on a sample (Zz) { that is, the generalization error:
GenErr(FF, (2:), D) sup Pnf).
feF
Group actions. We are interested in the setting where a group G acts by measurable bijective transformations over X and D, which can also be seen as a G-action over Z, denoted
3

---

by 9 - 9. X.g.Y), Y), where E G. Such actions can also be applied to points (x, f()) in the graph of functions f, transforming any f into g f. 1-gg- flg z). The set g G forms the orbit of f under the action of G. Note that although we treat. G as an abstract group throughout, we will sometimes abuse notation and use the same letter to also refer to the representations of G as transformations over the spaces in which X, Y, Z, f. live.
G G- {g-
Equivariant models. We are now in a position to specify the learning setup with equivariant models. We say that f E F is equivariant, if f= Further, we say that the hypothesis class is G-equivariant if all f E F are equivariant. Note that if the G-action over Y is trivial, that is, if we have g Y for all g E G,y E Y), then f being equivariant reduces to requiring f(g z) = f(x) for all g, In such a case the model is said to be invariant. Also note that f(z) being equivariant corresponds to f(x, y) = {(f(z),)) (2),,) being invariant under some suitable product G-action over X' x xy
Averaging over a set of transformations. Let G be set of transformations of 2. The G-averaged generalization error for arbitrary F by taking averages E, with respect to the natural probability measure P on G is as follows:
1 n Σ Egf(g Z,)),
GenErr (F, (Z,), D) sup Z)]
JEF
Note that the above equals GenErr(F, { D) F is composed of invariant functions.
Data commentation/Orbiie averaging. Following discussion above, it might be instructive to consider the case of data augmentation. Note that a data distribution which is invariant under some G-action can be created from any D by averaging over G-orbit:: we take to be a random variable uniformly distributed over a compact set of transformations G. Then let D(G) == G Sc 9 D. This is the distribution of the dataset obtained from D under G- Gaangeeetttion. Then we have by change of variables:
(en (Z.). D) GenErr(F, {Eg(g Z.J}. D(G)).
(3.1)
Note that the notions of orbit and averaging used above do not rely on the property that G group in order to be well-defined.
3.2 Partial and Approximate Equivariance
Since our analysis treats the general case where the model and/or data symmetries are not strict, we now state some basic attendant notions.
Error to equivariance function. We first need measure to quantify how far off we are from perfect equivariance. To do so, we can define function in terms of f(æ, y) as:
F G + [0, +00), ee(f.g) = llg f- flloo.
The crucial property hore that ee(s. g) = iff g f = f. Note that one could use other distances or discrepancies (e.g. like the & norm) directly in terms of f, using which we can measure the error between g and
More general sets of transformations. We can use ee(.) to precisely specify the notions of partial and approximate equivariance that work with. We consider the general case where the underlying transformations on (X, Y) still have a common label set G and are assumed to be bijective over X' and y, but don't necessarily form group. For >> 0 and f E F we consider the e-stabilizer
Stab. (g G
G ee(f.9) S Se).
is fairly easy to see that this subset automatically a group for 0, but most often will not be when > 0. The latter corresponds to partial symmetry and thus to the setting
We take Pe to be the uniform measure over G if G is finite, and the normalization of the Haar measure of G to G if G c G is positive measure subset of ambient locally compact group G.

---

of partial equivariance. On the other hand, if we consider specific hypotheses such that for some > we have Stab, (f) = for all f F, then we are working in the setting of approximate equivariance [59, 56].
Conditions on G. We conclude this section with remark the nature of G consider in our paper. In our bounds, we first restrict to finite G. However, this setting can be extended compact groups which are doubling with respect to a metric that respects the composition operation. That is, distance dg over G, such that da(gh, g'h) = d(g. g'). The main examples we have in mind are compact Lie groups such as 5 S (nOn), O(n), and their finite subgroups like Z/NZ, as well as their quotients and products.
4 PAC bounds for G-equivariant hypotheses
In this section, we study the generalization properties of equivariant models. More specifically, we derive PAC bounds for both exact and approximately G-equivariant hypotheses. But first, we present some preliminarics related to PAC bounds in what follows.
PAC learning bounds.
We follow the standard approach (such as that outlined in [10]). We start with the following concentration bound, where JF composed of functions with range [- M/2, M/2]:
en
P
sup (P- (P- R(F2) + - exp
(4.1)
M
where R2 (F) denotes the Rademacher complexity, which is given by
1 Σ a:J()Z),
R(Fz) := E. sup n.
and where ..,...,7, ~ D are i.i.d. samples and (o1:..., denotes the so-called Rademacher variable, which a uniformly distributed random variable over {-1, independent of the Z,'s. R(Fz) can be bounded using classical technique for bounding the expected suprema of random processes indexed by the elements of a metric space, variously called the Dudley entropy integral or the chaining bound. The result below proven in [45, Lemma 3] (also see slightly stronger results in [58, Thm. 17] or [6, Thm. 1.1])
3 V
dJam(J)
R(Fz) < inf a>0
a
VInN(F L, 1oo
(4.2)
Recall that for a metric space (x,, the covering number N(X, e, dx) is the smallest number of balls of radius required to cover X. In (4.2) we use the cover numbers of FF supremum distance, Lee. the distance between two functions f.g E F, F1 11 glloo = supsez [f(=) g(=))). It is known that by rescaling the fundamental estimate due to Kolmogoroo-Tikhoniree
[54, eq. 238, with s = 1, and eq. 1], and under the mild assumption that F is composed of 1-Lipschitz* functions on Z with values in an interval [-M M/2] for a centralizable metric space Z, the following holds
M (~+1) ++1)+N(Z,c/2)
N(2,2c) S Nog, 11 S log2
(4.3)
Before start stating our results, need to define few more notions:
Doubling and Hausdorff dimensions. If in a metric space (X, dx), every ball of radius R can be covered by at most À balls of radius R/2, the space has doubling dimension ddim(X)= = log, A. The doubling dimension coincides with the usual notion of (Hausdorff) dimension dim i.e. ddim dimX, in injectivity radius, in particular it equals d if X C RD is a regular d-dimensional submanifold or D d and X regular open subset such a ball a cube.
X is compact manifold with bounded
4 All of formulas generalize to classes of {-Lipschitz functions for general L > 0: the change amounts to applying suitable rescalings, see the Appendix for more details. This mild condition siguifies that for any open set U of diameter at most 2r there exists a point d so that U is contained in B(x", B().r)) r).
5

---

Discrete metric spaces. A metric space (X,dx) is discrete if it has strictly positive minimum separation distance 6x == minazz'ex (x > O. We then have
(XX,e) = min(,x))
(4.4)
which is especially relevant for finite groups G endowed with the word distance (i.e. d'(g.g"), which is the minimum number of generators required to express و g' for which dc = 1. Now, note that as straightforward consequence of the definition, there exists universal 0 such that 31]:
c)2,c) 2diam(
ddim
(4.5)
and by (4.3) we get the simplified bound (where implicit constants are universal):
In, e, llo) 4diam (2) ddim(2)
(4.6)
By all the above considerations, can bound the generalization error follows:
Proposition 4.1. Assume that = ddim(Z) 22 2, and 6 < 1/2, and let D == diam 2). Then for any probability distribution D of data over Z, with notation as in the beginning of Section 4, the following holds with probability at least 1 6:
4dd
Dd
1/a
GenErr(F, &
+ +n 1 ol log(2/6),
2
the implicit constant is independent of 6, n; only depending on through the constants in (4.5).
Due to space constraints, all our proofs are relegated to the Appendix. With the above background, we now first show generalization bounds under the more general notions of equivariance we have discussed.
4.1 Generalization bounds improvement under partial or approximate equivariance
In this section, we prove generalization error bounds with the notations and definitions from Section 3.2. We consider the following sets of transformations:
Stab. = Stab.(F) = (ta
fEF
We note that the strict equivariance case is recovered if, for =, have Stabo G. Proposition 4.2. Let Stab, be as above, and assume that |Stab.l > O. let 2 C 2 be a measurable choice of -orbit representatives for points in 2, and let G Z + 0 be the measurable map that associates to each z Z its representative
Z Let F = [f
f E F}} and let (D) represent the image measure of D. Then for each n E N, if (2 1 are i.tdd samples with Z, and ZZ,- == L Li, then we have
GenErr(F, () 2e (Sab.)) (F, (Z.). D) 2e GenErr(F! (Z, (D)).
The above result says that the gencralization crror of our setting of interest could roughly be obtained by working with reduced set of only the orbit representatives for points in Z. This is in line with prior work such as [51, 20, 41). However, note that our result is already more general and does not require that the set of trausformations form group. With this, we now need an understanding of the covering of spaces represenlatives 20 and the effect of Stab, on them. The answer is evident in case Stab, = G, that G, 2" are manifolds, and Z = z x G. Since ddim coincides with topological dimension, and we immediately have do d dim(G).
Intuitively, the dimensionality of G can be understood as climinating degroes of freedom -1/d
from Z, and it is this effect that improves generalization by n
We now stale simplified form of Theorem A.3, which is sufficient for proceeding further. Our results generalize [51, Thmn 3]: allow for non-product structure, possibly infinite sets of transformations that may not form a group, and we relax the distance deformation hypotheses for the action on Z).

---

Corollary 4.3 (of Thm. A.3). With the same notation as aboue, assume that for Stab. the transformations corresponding to the action of elements of Stab, satisfy the following for some I. > 0, and for choice of a set of representalives 2 c 2 of represendalives of Stabb-orbils:
1. For all 20, 2 E z and all g Stab, it holds that 20. 2/) 1 L d(g 20, g z1).
2. For all g.g' E Stab, it holds that dalg. g') - L dist(g .g z.)²
Then for each
there holds N S ((2,0//2))//((ttbbb..
To be able to quantify the precise generalization benefit we need bound on the quantity ((tab, 6). For doing so, we assume that Stab, is a finite subset of a discrete group G, or is positive measure subset of compact group G. As before, let |G] and dg denote IG and dG) respectively for finite G. Also, denote the Hausdorff measure and dimension by Vol(G) and dim(G) for compact metric groups. Note that the minimum separation åg is zero for dim(G)= 0. Then our covering bound can expressed in the following umbrella statement:
Stab,
Assumption: ((Stab,, 6) Z max (max (6, )
(4.7)
In order to compare the above to the precise equivariance case, we later use the factor
Stab_] E (0,
Dens(c) = G|
which measures the richness of Stab, compared to the whole ambient group G, in terms of ervor e. The fact that Dens(c) > 0 follows from assumption that |Stab.| 0. Furthermore, Dens(c) is always an increasing function of 6, as follows from the definition of Stab.. With these considerations on coverings, we can state a general result quantifying the generalization benefit, where if we set = 0, we recover the case of exact group equivariance.
Theorem 4.4. Let > 0 be fired. Assume that for a given ambient group G the almost stabilizers Stab, satisfy assumption (4.7) and that the assumptions of Corollary 4.3 hold for some finite L = Le > 0. Then with the notations of Proposition 4.1 we have with probability
GenEm([F [7,), D) S 11/2
1/2 /// log(2/0) + 26 (Fc);
where
do do/2+1
dg 8g
D2 1/2
if G is finite and ( < In 62
|Stab,
(E2)
do
(2L.) )d
Ddd
1/do
else.
du |ttab.In
The interpretation of the above terms is direct: the term 2e is the effect of approximate equivariance, and the term (E.) includes the dependence on |Stab.| and thus is relevant to the study of partial equivariance. In general the Lipschitz bound L, is increasing in e as well, since Stab, includes more elements of G as increases, and we can expect that actions of elements generating higher equivariance error in general have higher oscillations.
5 Approximation error bounds under approximate data equivariance
In the introduction, we stated that aim to validate the intuition that that model is best whose symmetry aligns with that of the data. So far we have only given bounds on the generalization error. Note that bounds hold for any data distribution: in particular, the bounds are not affected by whether the data distribution is G-equivariant or not. However,
Here dist(A, B) min(d(a,b) A.b E B} denotes the distance between sets, induced by d.

---

the fact that data may have fewer symmetries than the ones introduced in the model will have a controlled effect on worsening the approximation error, as described in this section.
However, controlling the approximation error has an additional actor in the fray to complicate matters: the distinguishing power of the loss function. Indeed, having degenerate loss function with a large minimum set will not distinguish whether the model is fit to the data distribution or not. Thus, lowering the discrimination power of the loss has the same effect as increasing the function space for which we are testing approximation error.
Assuming at first that F is composed of G-equivariant functions, we compare its ap- proximation error to the one of the set . of all measurable functions m X - y. Recall that f(Z) ((f(X),Y) Y) is a positive function for all E F, thus, denoting by M' := {F(x, = {(m(x),)). m E MM, the approximation error gap can be defined and bounded as follows (where F* M' is function realizing the first minimum in the second line below):
AppGap(F,D,
/EF AppErr(F, D) AppErr(M D) min [[ min R[F(Z))
FEM
W I
min E 2)]] - min B[F(Z)) 2 [F 2)]] - (Z)) FEM!
FEM
min (F Z F(Z)].
FEM
With applications to neural networks in mind, we will work with the following simplifying assumptions:
1. The loss function quantitatively detects whether the label is correct, iee we have (yy,y') 0 if y = y', and E(y.v') 2 spdy(y, v') for a strictly convex with =00)) = O, where dy is the distance on V. This assumption seemss reasonable for use in applications, where objective functions with strict convexity properties are commonly used, as they help for the convergence of optimization algorithuns.
2. The minimization across all measurable functions F = M produces a zero-risk solution, Le.. minreM' [[F(Z)]
O is achieved by a measurable function y" + y. By assumption 1, this implics that D is concentrated on the graph of y" This assumption corresponds to saying that the lcarning task is in principle deterministically solvable. Under this assumption, the task becomes to approximate high accuracy the (unknown) solution y".
With the above hypotheses we have
AppGap(F, D) = AppErr(F, D) 2 min Ez(E,[F(r Z)]].
FEM
As a slight simplification of Assumption for ease of presentation, we will simply take y = T and (ly,5') = dy y²2² below. Note that Assumption 1 directly reduces this case, as a strictly convex sp()) with (0)) = 0 as in Assumption 1 is automatically bounded below by a multiple of 1
Now, with the aim to capture the mixed effects of approximate and partial equivariance, we introduce the following set of model classes. For e 2 0, E (0, 1]:
C.. f=== =FFCM' Dens(c) = Stab (F)
2 1
G
In order to establish some intuition, note that St) increasing in and as a consequence Cx.e is also increasing in Directly from the definition one finds that Stab (F) is necessarily subgroup of G, and thus we allow e 0, which allows more general sets of symmetries than just subgroups of G. The most interesting parameter in the above definition of C., is X, which actually bounds from below the 'amount of prescribed symmetries' for our models. In the fully equivariant case = 0, = 1, we have the simple description Co = F ( (M())), whose maximal element is (M However in general C.,x will not have unique maximal element for < 1: this due to the fact that two different elements Fi F2 C., may have incomparable stabilizers, so that (Ft) Stab, > 0 and (Fr) Stab > 0, and thus Fi J. & C... Our main result towards our approximation error bound the following.
8

---

Proposition 5.1. Assume that (J.dy) is compact metric space and consider Ely. V/) dy(y.y')² Fix 2 0. Then for each X E (0, there erists an element F E Cr,x and measurable selection d X X of representatives of orbits of X' under the action of (F), such that if X 9 are random variables obtained from X ~ DD by imposing x : o and X = g- xb, then we have
AppErr(F, Exp min 1axx [Inax {dy (g (.. y, v2 x2)) -, 07)
In the above, as increases, we see decrease in the approximation gap, since in this case model classes FF allow more freedom for approximating y* more accuratcly. On the other hand, the effect of parameter À is somewhat more subtle, and it has to do with the fact that as decreases, (Ja)(()) for F E C,,, can become smaller and the allowed oscillations of y" x²) are more and more controlled.
Now to bound the approximation error above using the quantities that we have been working with, will use the following version of an isodiametric inequality metric groups G. As before we assume that G has Hansdorff dimension dim(G) > 0 which coincides with the doubling dimension, or is discrete. By [X] we denote the Hausdorff measure of X G if dim(G) > or the cardinality of X if G is finite. Then there exists an isodiametric constant CG depending only on G such that for all X C G it holds that
X G
2 A
dX) CGA 1/dd/mmmm
(5.1)
The above bound can be obtained directly from the doubling property of G, applied to cover of X via a single ball of radius diam(X), which can be refined to obtain better and better approximations of [X]. We can now control the bound from Proposition 5.1 as follows:
Theorem 5.2. Assume that (Y, dy) is a compact metric space and Ely, = = (d)(u.//)². Let G be compact Lie group a finite group, with distance dg. Let ddim(G) be the doubling dimension of G, and assume that for all E G such that the action of over X is defined, it holds that d(g g. xx) L'd g'). Then, there erists constant CG depending only G such that for all E 1) and e >> O, there erisls an element F E C..x where for any dala distribution D, y² can be chosen Lipschitz with constand Lip(y"). We have
AppErr(F,D) & (max (max(Co L'
()d//dmm()))) c,, 0))²
We note that, given our proof strategy of Proposition 5.1, we conjecture that actually the above bound is sharp up to constant factor: minrec,, AppErr(F, (F,D) D) may have a lower bound comparable to the above upper bound. The goal of the above result is to formalize the property that the approximation error guarantees of F will tend grow as the amount of imposed symmetries grow, measured by X.
6 Discussion: Imposing optimal equivariance
We have so far studiod bounds on the generalization and the approximation errors, each of which take very natural form in terms of properties of the space of orbit reprosentatives (and thus the underlying G). One of them depends on the data distribution, while the other doesn't. Using them we can thus state result that quantifies the performance error, or gives the (and their respective symmetries). Define the performance error of model class F E Cr,
trade-off, of a model based on the data distribution
over an i.ddd sample {2 Z, ~ D as
PerfErr (F, (2,) D) == GenErr(F, (Z.), D) + AppErr(F, D)-
Combining Theorems 4.4 and 5.2, we get the following:
Theorem 6.1. Under the assumplions of Theorems 4.4 and 5.2, we have that, assuming all the function classes are restricted to functions with values in (-M,AN M), then there erist
9

---

values C1. C2 C3 > depending only on du, (2LD)*/IG], |G], and C C such
that with probability at least 5,
ifnd 2 C3, { Ci (1x)117
1/2 1//2 M ( 11 C2 1J1/40 PerfErr(F S
in A < C3.
Note that the above bounds are not informative as A + 0 for the continuous group case, which corresponds the second option in Theorem 6.1. This can be sourced back to the form of Assumption (4.7), in which the covering number on the left is always 2 1, whereas in the continuous group casc, the right-hand side may be arbitrarily small. Thus the result is only relevant for À away from 0. If we fix c 0 and we optimize over À E [0. in the above bound, we find a unique minimum X for the error bound, specifying the optimum size of Stab, for the corresponding case (see the Appendix for more details). This validates the intuition stated at the onset that for the best model its symmetries must align with that of the data. As an illustration, for C, Cr C2 0.04 and C33 = 0.01 with n 1000000, the error trado-off is shown on the figure on the right.
bergen
Concluding Remarks
Error versus lambda for large n for fixed values of C,C1, Cs.
In this paper, we have provided general quantitative bounds showing that machine learning models with task-pertinent symmetrics improve generalization. Our results do not require equivariance. We also
the symmetries to be group and can work with partial/approxing presented a general result which confirms the prevalent intuition that if the symmetry of model is mis-specified w.r.t to the data symmelry, its performance will suffer. We now indicate some important future research directions, that correspond to limitations of our work:
@Model-speciffi bounds) While in Theorem 6.1 we obtain the existence of an optimal amout X without hopes to be sharp in such generality, we may expect that if we restrict to specific tasks, the bounds can become much tighter, and if so, the value X of optimal amount of symmetries can become interpretable and give insights into the structure of the learning tasks.
(Tighter bounds beyond classical PAC theory) For the sake of making the basic principles at work more transparent, we based our main result on long-known classical results. However, tighter data-dependent or probabílistic bounds would be very useful for getting a sharper value for the optimal value of symmetries X via a stronger version of Theorem 6.1.
(Beyond controlled doubling dimension) Our focus here is groups G of controlled doubling dimension. This includes compact and nilpotent Lie groups, and discrete groups of polynomial growth, but the doubling dimension is not controlled for notable important cases, such as for the permutation group S, (cf. section 3 of [17]) or for the group (Z/2Z)². In order to cover these cascs, it will be interesting to build analogues of our main result based on other group complexity bounds, beyond the doubling dimension case.
Acknowledgments and Disclosure of Funding
The authors thank Arych Kontorovich for readily answering questions (and supplying references) about Beanoggrov-Tikhominng queries and providing a copy of his dissertation before appeared online. MP thanks the Centro Nacional de Inteligencia Artificial in Chile for support, as well as Fondecyt Regular grant number 1210462 entitled "Rigidity, stability and uniformity for large point configurations".
and Bryn Elesedy for graciously answering
10

---

References
[1] Yaser S. Abu-Mostafa. Hints and the VC Dimension. Neural Computation, 5(2):278-25) 288, 03 1993.
[2] Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlchh-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
33 Fabio Anselmi, Joel Z. Leibo, Lorenzo Rosasco, Jim Mutch, Andrea Tacchetti, and Tomaso A. Poggio. Unsupervised learning of invariant representations in hierarchical architectures. CoRR, 0bbs/331.41158 2013.
[4] Fabio Anselmi, Lorenzo Rosasco, and Tomaso Poggio. On invariance and selectivity in representation learning. Information and Inference: A Journal of the IMA, 5(2):134-158, 05 2016.
5) Minkyung Back, Frank Dimaio, Ivan V. Anishchenko, Justas Dauparas, Sergey Ovch- innikov, Gyu Rie Lee, Jue Wang, Qian Cong, Lisa N. Kinch, R. Dustin Schaeffer, Claudia Millán, Hahnbeom Park, Carson Adams, Caleb R. Glassman, Andy M. De- Giovanni, Jose H. Pereira, Andria V. Rodrigues, Alberdina Aike van Dijk, Ana C Ebrecht, Diederik Johannes Opperman, Theo Sagmeister, Christoph Buhlheller, Tea Keller,Keller, Manoj K. Rathinaswamy, Udit Dalwadi, Calvin K. Yip, John E. Burke, K. Christopher Garcia, Nick V. Grishin, Paul D. Adams, Randy J. Read, and David Baker. Accurate prediction protein structures and interactions using a three-track neural network. Science, 373:871 - 876, 2021.
6 Peter Bartlett. Covering numbers, chaining & dudley's 's entropy integral (lecture 24). class notes on statistical learning theory, 2006.
77] Arash Behboodi, Gabriele Cesa, and Taco S Cohen. pac-bayesian generalization bound for equivariant networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advunces in Newral Information Processing Systems, volume 35, pages 5654-5668. Curran Associates, Inc., 2022.
8 Erik J. Bekkers. B-spline cnns lie groups. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview net, 2020.
99 Alberto Bictti, Luca. Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in newral information processing systems, 34:18673- 18684, 2021.
[10] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. Advanced Lectures on Machine Learning: ML Summer Schools 2003, Conberra, Australia, February 2-14, 2003, Tübingen, Germany, August 4-16, 2003, Revised Lectures, pages 169 207, 2004.
[11] Anadi Chaman and Ivan Dokmanic. Truly ihitt-invariant convolutional neural net- works. In Proceedings of the IEEE/CC CEE//VV Conference on Computer Vision and Pattern Recognition, pages 3773 3783, 2021.
[12] Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A groupetheoretic framework for data 2020.
augmentation. The Journal of Machine Learning Research,
[13] Taco Cohon, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolutional networks and the icosahedral cnn. In ICML, 2019.
[14] Taco Cohen and Max Welling. Group equivariant convolutional networks. In ICML, 2016.
[15] Taco S. Cohen. Learning transformation groups and their invariants. Master's thesis, University of Amsterdam, 2013.
11

---

[16] Taco S Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant CNNs on homogeneous spaces. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[17] Michel Deza and Tayuan Huang. Metries on permulations, a survey. Journal of Combinalorics, Information & System Sciences, 23(1-4):173- 185, 1998.
[18] Stephan Eismann, Raphael J. L. Townshend, Nathaniel Thomas, Milind Jagola, Bowen Jing, and Ron O. Dror. Hierarchical, rotation-equivariant neural networks to select structural models of protein complexes. Proteins: Structure, 89:493 501, 2020.
[19] Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. Advances in Neural Information Processing Systems, 34:17273-17285 2021.
[20] Bryn Elesody. Group symmetry in PAC learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
[21] Bryn Elesody. Symmetry and Generalisation Machine Learning. PhD thesis, University of Oxford, 2023.
[22] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2959-2969. PMLR, 2021.
[23] Mare Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft oquivariance constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neurol Information Processing Systems, volume 34, pages 30037-30049. Curran Associates, Inc., 2021.
[24] Mare Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivariant multilayer perceptrons for arbitrary matrix groups. ArXiv, abs/2104.094558 2021.
[25] Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Per- mutation equivariant models for compositional generalization in language. In ICLR, 2020.
[26] B. Haasdonk, A. Vossen, and H. Burkhardt. Invariance in kernel methods by haar- integration kernels. In Heikki Kalviainen, Jussi Parkkinen, and Arto Kaarna, editors, Image Analysis, pages 841-851, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[27] Osman Semih Kayhan and Jan C van Gemert. On translation invariance in cnns: Con- volutional layers can exploit absolute spatial location. In Proceedings of the IEEE/CVF Conference Compuler Vision and Pattern Recognition, pages 14274 14285, 2020.
[28] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. ArXiv, abs/ abs//200.03123, 2020.
[29] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolu- tion in neural networks to the action of compact groups. In ICML, 2018
[30] Aryeh Kontorovich and Roi Weiss. Maximum margin multiclass nearest neighbors. In International conference on machine learning, pages 900. PMLR, 2014.
[31] Robert Krauthgamer and James R Lee. Navigating nets: Simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-STAM symposium on Discrete algorithms, pages 798 807. Citeseer, 2004.
(32] Yann André LeCun, Bernhard E. Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne E. Hubbard, and Lawrence D. Jackel. Backpropagation applied to handwritten zip code recognition. Newral Computation, 1:541-551 1989.
12

---

[33] Clare Lyle, Mark van der Wilk, Marta Z. Kwiatkowska, Yarin Gal, and Benjamin Gloem-Reddy. On the benefits of invariance in neural networks. ArXio, abs/2005.00172 2020.
[34] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv,
009002, 2019.
[35] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3351-3415 3418. PMLR, 15-19 Aug 2021.
(36] Marvin Minsky and Seymour Papert. Perceplrons, Expanded Edition: An Introduction to Computational Geometry. The MIT Press, Cambridge, MA, 1987.
[37] Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nathan Srebro. A pac-bayesian approach to spectrally-normmalized margin bounds for neural networks. ArXio, abs/1707.09564 2017.
(38) Siamak Ravanbakhsh, Jeff G. Schneider, and Barnabás Póczos. Equivariance through parameter-sharing. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, TCML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2892 2901. PMLR, 2017.
[39] Marco Reisert and Hans Burkhardt. Learning equivariant functions with matrix valued kernels. Journal of Machine Learning Research, 8(15):385-408, 2007.
[40] David W Romero and Suhas Lohit. Learning partial equivariances from data. Advances in Neural Information Processing Systems, 35:36466-3644 2022.
[41] Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group invariant / equivariant deep networks via quotient feature spaces. In Cassio P. de Campos, Marloes H. Maathuis, and Erik Quaeghebeur, editors, Proceedings of the Thirty-Seuenth Conference on Uncertainty in Artificial Intelligence, UAI 2021, Virtual Event, 27-30 July 2021, volume 161 of Proceedings of Machine Learning Research, pages 771 780. AUAI Press, 2021.
[42] Victor Garcia Satorras, E. Hoogeboom, F. Fuchs, I. Posner, and M. Welling. E(n) cquivariant normalizing flows for molecule generation in 3d. ArXio, abs/2105.09016, 2021.
[43] Bernhard Schölkopf, Chris Burges, and Vladimir Vapnik. Incorporating invariances in support vector learning machines. In Christoph von der Malsburg, Werner von Seelen, Jan C. Vorbrüggen, and Bernhard Sendhoff, editors, Artificial Neural Networks ICANN 96, pages 47-52, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.
[44] H. Schulz-Mirbach. On the existence of complete invariant feature spaces in pattern recognition. In Proceedings., 11th LAPR International Conference Pattern Recognition. II.. Conference B: Pattern Recognition Methodology and Systems, pages 178-182, 1992.
(45] Han Shao, Omar Montasser, and Avrim Blum. A theory of PAC learnability under transformation invariances. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[46] John. Shawe-Taylor. Building symmetries into feedforward networks. In 1989 First IEE International Conference on Artificial Neural Networks, (Conf. Publ. No. 313), pages 158 188-122,111 1989.
(47] John Shawe-Taylon Threshold network learning the presence of equivalences. Tn NIPS, 1991.
13

---

[48] John Shawe- Shywe-Taylor. Symmetries and discriminability in feedforward network architec- tures. IEEE Transactions on Neural Networks, 4(5):816 1208866666,,, 1998.
[49] John Taywor. Introducing invariance: a principled approach to weight sharing. In Proceedings of 1994 IEEE International Conference Newral Networks (ICNN'94) volume 1, pages 343-349 vol.1, 1994.
[50] John Thylor Sample sizes for threshold networks with equivalences. Information and Compulation, 118(1):65 72, 1995.
[51] Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of invariant classifiers. In Artificial Intelligence and Statistics, pages 1094 1103. PMLR, 2017.
[52] T. Sosnovik, A. Moskalev, and A. Smeulders. Scale equivariance improves siamese tracking. 2021 JEEE Winter Conference Applications of Computer Vision (WACV), pages 2764 2773, 2021.
[53] Behrooz Tahmasebi and Stefanie Jegelka. The exact sample complexity gain from invariances for kernel regression manifolds, 2023.
[54] Vladimir M. Tikhomirov. s-entropy and e-capacity of sets in functional spaces. Selected Works of AN Kolmogorow: Volume III: Information Theory and the Theory of Algorithms, pages 160, 1993.
[55] Raphael J. L. Townshend, Stephan Eismann, Andrew M. Watkins, Ramya Rangan, Maria Karelina, Rhiju Das, and Ron O. Dror. Geometric deep learning of rma structure. Science, 373:1047 1051, 2021.
[56] Tycho F. A. van der Ouderaa, David W. Romero, and Mark van der Wilk. Relaxing equivariance constraints with non-stationary continuous filters. In Advances in Newral Information Processing Systems (NeurIPS), volume 35, Dec 2022.
[57] Andrea Vedaldi, Matthew Blaschko, and Andrew Zisserman. Learning equivariant structured output svm regressors. In 2011 International Conference on Computer Vision, pages 959 966, 2011.
[88] Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with lipschitz functions. J. Mach. Learn. Res., 5(Jun):669-66) 669-666999666666 2004.
[59] Rui Wang, Robin Walters, and Rose Yu. Approximately equivariant networks for imperfectly symmetric dynamics. In International Conference on Mochine Learning, pages 23078 23091. PMLR, 2022.
[60] Maurice Weiler, Patrick Forré, Erik P. Verlinde, and Max Welling. Coordinate independ- ent convolutional networks isometry and gauge equivariant convolutions on riemannian manifolds, ArXiv, abss/2106.065 .00000, 2021.
[61] Jennifer C. White and Ryan Cotterell. Equivariant transduction through invariant alignment. In Proceedings of the 29th International Conference on Computational Linguislies, pages 4651-44400 1655-4663, Gyeongju, Republic of Korea, Oct. 2022. International Committee on Computational Linguistics.
[62] Marysia Winkels and Taco Cohen. Pulmonary nodule detection in ct scans with equivariant cnns. Medical image analysis, 55:15-26 26.1-266,2 2019.
[63] Jeffrey Wood and John Shawo-Taylor. Theory of symmetry network structure. Technical report, 1993.
[64] Jeffrey Wood and John Shawe- Representation theory and invariant neural networks. Discrete Applied Mathematics, (1()3333660, 1996.
(65] Jeffrey Wood and John Shawe- Shawe-Taylor. unifying framework for invariant pattern recognition. Pattern Recognition Letters, (7(14):1415-1423) 1996.
14

---

[66] Yinshuang Xu, Jiahui Lei, Edgar Dobriban, and Kostas Daniilidis. Unified fourier-based kernel and nonlinearity design for equivariant networks on homogeneous spaces. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, TCML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 24596 24614, PMLR, 2022.
[67] Sicheng Zhu, Bang An, and Furong Huang. Understanding the generalization benefit of model invariance from data perspective. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Newral Information Pro- cessing Systems, volume 34, pages 4328-4341. Curran Associates, Inc., 2021.
[68] Xupeng Zhu, Dian Wang, Ondrej Biza, Guanang Su, Robin Walters, and Robert Platt. Sample efficient grasp learning using equivariant models. CoRR, abs/ abs/2202 09068, 2022.
15

---

A Proofs
A.1 Proofs of results from Section 4
A.1.1 Proof of Proposition 4.1
Proof.
Reformulating (4.1) we find that with probability at least 1-6 it holds that:
v2 1l (2/()
sup (P Pa)fI S R(F2) FEF
(A.1)
vn
the first line of (4.2) is the one for which 3 In,[((FF a, || ll Keeping in mind (4.6), we choose a diam 2 ) aiiz in (4.2), which gives (abbroviating d = ddim diam
Next, we compound the bounds for R(F2). The optimum
f T --2
R(Fz) x D/n
+ 1122
(D/t) D D/ (D/n
Dn-1/a
n-1/d
D n//d
2
1
2
Now the last equation and equation (A.1) yield the claim.
A.1.2 Proof of Proposition 4.2
We start with preliminary result under hypotheses of strict equivariance. In this case, we are able use change of variables reduce the generalization error formula an equivalent one depending only on measurable choice of G-orbit representatives of elements from 2:
Proposition A.1. Let F be a set of G-inwariant functions, and let 2 C Z be a choice of G-orbil represenlalives for points in 2, such that 1 Z - 2 associaling lo each orbil represenlalive. 20, is Borel measurable. Let F == U1|2a E F} and denole by (D) the image measure of D. Then for each n E if [Z are iid. samples with Z4 ~ D and 2 = L Zi, have
ils
GenErr(F, (Z,), = GenEr O (F, (F,(Z),)) = GenErr(F), (,
Proof. For the first equality, we use the definition of GenErr and the change of variable formula (3.1) and the fact that G-invariant functions satisfy f(Z) - 7)]. For the socond equality, note that by hypothesis, for cach f E F we have f(z) f(g 2) for all
E G, E Σ, in particular f(=) = f()((z) and we conclude by a change of variable by the map 0 in the expectations from the definition of (e)
Now the proof Proposition 4.2 combines the above idca with a simple extra step:
Proof of Proposition 4.2: The proof uses the triangular inequality. For F and g Stab,
we have:
m Σ f(z))
n
Pf P.fl [[)
Eg f(2))
+ f flloo Σ 9 f(z,)
By averaging over g E Stab,, we obtain the incquality in the statement of the proposition. The equality follows by a change of variable via map 6, exactly as in the stratogy of Proposition A.I.
A.1.3 Proof of Corollary 4.3 and of the more general result of Theorem A.3
In order to make the treatment better digestible, we first consider the intuitively simpler case of strict equivariance, and then describe how to extend it the more general case of approximate and partial equivariance. In this case, if we restrict our equivariant functions to only the space of orbit representatives 20, the dimension counts from classical generalization bounds of Proposition 4.1 improve follows:
16

---

Corollary A.2. Assume that F is composed of G-inwariant functions and that do == ddim(2") >>>>> 2. Also, denote Do := diam( 2 With the same notation as in Proposition A.1 and with the hypotheses of Proposition 4. for any probability distribution 'D over 2, the following holds with probability least 1 8:
1/do
2 do
D
GenErr(F, (())
+
1/2 1
1o (2/()/
do
n
Proof. Due to Proposition A.1, we only need to bound GenErr(F") (27), (DD)). Thus it suffices to apply Proposition 4.1 for the above function. We note that || 11 S [| to conclude.
The drawback of the above Corollary, that it leaves open the question of how to actually bound the diameter and dimension of 2 on which we do not have direct control. The next steps we take consist precisely in translating the information from properties of G to relevant properties of n
first, simpler, approach could be the following. Under the reasonable assumption that 2, z have diameter greater than 1, the leading term the left in Corollary A.2 is n - Thus the optimal choices of z are those which minimize the doubling dimension do = ddim (2)) amongst sets of representatives of G-orbits. This is a weak regularity assumption, implying that we want 2 to not oscillate wildly. The effect of G on coverings is evident in case G, 2 are manifolds, and Z 2 x G (see (A.3) for the strictly equivariant case, and the more general (A.5) for the general case). Since ddim coincides with topological dimension, we immediately have
dg = d dim(G).
Intuitively, the dimensionality of G can be understood as eliminating degrees of freedom from 2, and it is this effect that improves generalization by n-1/ld-dim(G)) -1/d
In order to inchude more general situations, we now describe a second, more in-depth approach. We take step back and rather than addressing direct diameter and dimension bounds for 20, we go 'back to the source' of Proposition 4.1. We update the bounds on covering numbers of g0, directly in terms of the G-action and of Z. The ensuing framework is robust enough to later include, after few adjustments, also the cases of partial and approximate equivariance. Here is our fundamental bound, which generalizes and extends [51, Thm.3).
Theorem A.3. Assume that Z is a metric space with distance d and S C G is a subsel of metric group G consisting of transformations g 2 2 (with action denoted 2 == g(=)) for which there erists choice of S-orbit representatives Zo Z and a distance function d on S satisfying the following for L, L' E (0, +oo] (with the conventions 1/ + 00 == 0 and (x, == (X,, +20) = =00)
1. For all 20, 2 E Zo and all g E S it holds that 4, 26) S d(g 20, g22() < L' L'd 26).
2. For all g.g E S and 2o, #0 E Zo it holds that dda(g.9') S d(g zo.g' =)) S L'da(g.g'),
Then for ench 8' > the following holds
N(2.. 28' 28' (S, N(2 S N2 8 (S 8 /2L)).
(A.2)
Before the proof, observe how Corollary 4.3 can be recovered using the choice L >> 0, too in Theorem A.3:
Proof of Corollary 4.9: We apply Theorem A.3 to Stab, and 2, = - as in the corollary statement. Then we take 8 = 2L8 in the conclusion (A.2), and consider only the lower bound inequality, which directly gives the claim of the corollary.
Proof of Theorem A.I: In this proof, we will denote a minimal a-ball cover of metric space X by X..
17

---

Note that we are not assuming G to be group, but due to lower bound in property 1. it follows that 2n + g 2g is injective (for 2n F 2 we have d(zg, z > 0 and thus g 20 # g -2)), and when below we write "g-1r Ir this has to be interpreted as the inverse of the g-action,
restricted to its image.
Further, note that the case when one of L, L' is to0, corresponds to removing the part of the assumptions (and of the conclusions) involving that value, thus we only consider the case of finite L' and finite L.
On fixing an arbitrary point E Z, we can write = g- 2a for suitable g E G. E 2 Let 17 := /2/2L'. For fixed covers Zg: Gy, there exists a point z E Zn with d( 20) < 1 and g' E G2 with de(g' .)) < 7. Thus by property 1. we have d(g 2) < L'' = c/2 and by property 2. we have d(g' =u. (6)) < I'n = 8' /2. By the triangle inequality, d(g' 2 2) < 8 and thus GG 2 is an o'-cover of Z. Thus we have
N(2,8') S #G /21/ #28
optimizing over the cardinalities the right hand side yields the second inequality in (A.2).
Now consider an 8'-cover Zz of Z, and for n 28L consider an cover G, of G. We find that for each E Zg,, there exists at most one g E G, such that dist(z, Zo) < n/2L = 8' Notice that if this were false, we could use the triangle incquality and contradict property 2. in the statement. For cach g G2 denote Zg the set of such points 2 E Z such that there exists x E g 20; and assign exactly one such x = s=z)) to each 2, forming a set Xg of all such z(z). Any other point x' E g z such that d(z', 2) < 8' then satisfies d(x', x) < 28' by triangle incquality, and thus Xg is -over of g. Zo. If for g-20 E g g.Xo the point
g. No
satisfies d(g 20, xr) < 28', then by property 1. in the statement we have d(zo, - xx) < 28' L, and thus 9 -1. Xg a 28 L-cover of Zo. having the same cardinality as Zg. We then compute as follows, proving the first inequality in (A.2):
N(2,0') > Σ #2g
Σ #(g Xx)) 2 28, 2). gEG,
gEGn
A.1.4 Proof of Theorem 4.4
As before, we focus again first on the exact equivariance case, where Theorem A.4 is the direct analogue to (or special case of) Theorem 4.4.
Under the hypotheses of Theorem A.3 on the G-action, we directly obtain the following, for the strictly equivariant case:
O) < 8(2,6/2L)
(A.3)
We next impose that for 8 S di) the group G satisfies the natural 'volume growth" assumption, where for compact groups Vol(G) is its dimenn)dimaaiio Hausdorff mcasure and dim is the usual Hausdorff dimonsion, and for finite groups we use minimum scparation notation &G > 0 as defined in (4.4):
#G/ #G/(max (6, dG)) dddimi)) if G finite,
Assumption: N(G,8)
(A.4)
/ddim)
if dimG > 0.
Similarly to Proposition 4.1, we then get the following, in which the leading term in the bound has exponent figuring do = ddim(2) Z) dim( Recall that dim(G) 0 for finite groups, thus the distinction can be made directly in terms of the dimension of G.
Theorem A.4. Let d > 0 be fized. Assume that for a given ambient group G the group G satisfies assumption (A.4) and that its action satisfies the the assumptions 1. and 2. of Theorem A.9 for some finâte L > O and L' = +00. We denote de = ddim G)) G is discrete group and dG dim(G) if G is compact and non-discrete, and
ddim( Z). Furthher assume do := d de > 2. Purthermore, set [G| == Vol(G) if dimG > 0 and G == #G for finile G.
Then with the nolations of Proposition 4.1 we have with probability 2 1
GenErr(F, (Z,), D) S 1/2
1/2 lo + (E),
18

---

where
dn
G
do/2+1
((2))= |G|n
1/2
if G is finite and (2L) < Glnn 6/
(F)
da
(2
1/do
otherwise.
do -2
[G/p
Proof. We follow the same computation as Proposition 4.1, but use Proposition A.1 in order lo reduce to restrictions of functions to 2". In this case, using (A.3) and assumption (A.4), and with notation as in our statement, we will have:
(2L)
2(
max (dc; :)-
G
where we have 8G = 0 for dimG >> 0. We set C (2 for simplicity of notation. In case |o|
Co 1 (which includes the case dimG's 0), we take (ddn))/do in the Dudley integral (4.2) and find
[ VCt
R(F2o) a aa+n
from which the proof goes exactly as in Proposition 4.1, with C replacing Dd, and we get the second option for the value of (E) as given in our statement. In case C& < instead we take a and our above bound for N(z,, plugged into (4.2) (recalling the notation for C):
R(Fzo) 2 1. VC
V max
ma, t)
= 55 5-d0/2+1 VC/n+ VC/n
t- /-do/2 2d,
ba
from which the second case of the value of (E) follows by direct computation.
Now the proof of Theorem 4.4 proceeds in exactly the same manner as the above. Below we explain the required adaptations:
Proof of Theorem 4.4: The following updates are the principal adaptations required for the above proof of Theorem A.4:
The role of G should be replaced by Stab,, except for the fact that parameters dG, do remain unchanged (i.e. we use their values corresponding to 'ambient' group G rather than those for Stab.).
The G-orbit representative set 2 then should be replaced by representatives z for orbits of Stab..
With these changes, assumption (A.4) implies its more general version, assumption (4.7). Indeed, |G] equals #G for finite G and Vol(G) for compact G, and 8G only in the first case. Furthermore, we have dstab, 2 &g as direct consequence of Stab, S G.
We observe that Corollary 4.3 (which also obtained from Theorem A.3 with the above two main substitutions) directly gives the version of Theorem (A.3) required to get the correct replacement of (A.3) under our initially declared two substitutions, We get:
N22,6/2L)
NZ22. S N(Stab,,
(A.5)
With the above changes, the proof follows by exactly the same steps in the above proof of Theorem A.4.
Remark A.5. Note that, as might be evident from the last proof, we could have introduced new more precise parameters to keep track of dimensionality and minimum separation for
Stab, rather than formulating assumption (4.7) terms do, &g. This justified for the aims of this work. Indeed, all the main situations of interest to us are those in which Stab, 'large" subset of G, iee. it has dimension da, and in all our examples for finite groups ōg > 0, the minimum separation for Stab, is within small factor of &g itself.
19

---

A.2 Proof of Proposition 5.1
Proof. We have that Z = (X, Y) is a data distribution in which by our assumption preceding the proposition, we have that almost surely Y y* (X) for deterministic function y". With this notation, we may write
[x[ = By xy [f x X., X2]]-
Recalling that we restrict to functions of the form f(x, = (f((), (2)) v)² we first consider the precise equivariance case t = 0. In this case for E (JF) we find also f(g -() = g f(xx)) and thus when optimizing over f we have to determine the optimal value of y y= fXX) to be associate to each X Thus consequence of all the above, if F would be the class of all precisely Stab--equivariant measurable functions, we would get the following rewriting:
AppGap(F, D) min E2|dy (f(d))((X))))) (X)) Ex min g [dyl y. (g x29 (A.6)
fEF
yEy
For é <> 0, for cach fixed X = x. we may further perturb the associated y = f(m?) by at most in the direction of y (X"), while still obtaining measurable function with approximation loo -o-nor error bounded by thus the above bound is improved to
AppErr(F; D) S Exy min min o| [dy(( y. v x2) =
(A.7)
as desired. In case F contains a strict subset measurable invariant functions with error e, we would only get an inequality instead of the first equality in (A.6) but we still have the same bound as in (A.7), and thus the proof is complete.
A.3 Proof of Theorem 5.2
Proof. We use the isodiametric inequality (5.1) in G, applying it to Stab. for F E Ce.A- Then by taking (F) X which is optimal for inequality (5.1) we can saturate the two bounds (modulo discrctization errors for discrete G) and we get
Stab X, diam(Stab.(F)) ~ CoA 1/ddim(0) G|
We next use Lipschitz deformation bounds and find that. for all X we have diam (g (g.x): g E Stab, (F)} < diam(Stab, (F)) Lip(y") L' CCA1/ddim(() ((F)) Lip(y") L'.
Then we use Proposition 5.1 for F and observe that when g, X are random variables as in the proposition, in particular g E Stab.(F) and for each X x! find the following estimate valid uniformly over {v" (g x²): g e Stab. (
dy(u. V (g 2)) s C Idddim(G) Lip(y") L'.
In similar way, also find
dy(v.9 4) CGAA/ddim(G) L'.
By triangle inequality, and using the assumption that Lip(y") ) ~ 1 it follows that
dylu.v (g 2 s Co CCX1/ddlm(G) (1 + Lip()" )) & C/X1/ddmm(G) Lip(y") ) E/.
Then we may perturb each y by e in order to possibly diminish this value without violating the condition defining Stab, (F), and with these choices obtain the claim.
20

---

A.4 Finding the optimal À = X for the bound of Theorem 6.1
We note that X minimizing CX* + C²X-8 for a, B is given by
B C
1/(++0)
recall that in our have the following choices, for case 1 and case 2 in the theorem's statement.
01 = 02 =1/d
B1 = 1/do-
and
C CoLip(y")L', (2LD)4/2/G11/2
C
&g 2d122)122
C2 (2LD) | /G
and thus the optimal choice of is
2dc/
2
(2LD)4/2G))
in case nd 2 C3, A
n aada/(datt +2)
dG 6G
22/2
in case nd > C3, = (2LD)d/do d/ 2 (dda/(dotde) 71 do/ (do)))
do
dG
B Examples
We describe some concrete examples of partial and approximate equivariance using the language we used section 3.2 while sourcing them from existing literature. But first, we expand little cquivariance error notation.
B.1 Equivariance error notation
Recall that the action of elements of an ambient group G over the product space = X x y may be written as follows: For coordinates
y we may write g = (g 2, y), and
thus for f: X y and f(x,y) ((((x) ,), we have the action
(g f)) = f(g 2) eF(gg z).9-
For the equivariance error of g. interpreted as 'the error of f's approximate equivariance under the action by g", we get the following, which is valid in the common situations in which E(y, v/) 2 0 in general with E(y, = 0 for all y E V:
ee(J.g) = I1g o1 sup e( x). v) (f(x)) v) 2 sup ([Ty x).g A(x)), (B.1)
2.y
where the last inequality follows by restricting the supremum from X' y to the graph of f. namely by imposing y = f(x).
In several recent works, the equivariance error is defined simply by comparing g- F(x jandf(g x), as in the rightmost term of (B.1), thus it is lower than the one found here. We provide justification for our definition of the equivariance error:
The loss L is the integrative part of the model, thus a definition for equivariance error which does not include will only detect partial information coucerning the influence of symmetries.
The notion of equivariance error defined via simplifies the comparison between and data distributions D.
21

---

B.2 Examples
B.2.1 Imperfect translation equivariance in classical CNNS
We consider here the most common examples group equivariant convolutional networks (GCNNs), which are the usual Convolutional Neural Networks (CNNs) for computer vision tasks. We follow observations from [27] and [11], and connect the underlying ideas to Theorem 6.1.
Setting of the problem. We consider a usual CNN layer, keeping in mind segmentation task, where both X' y represent spaces of images. More precisely, we think of images as pixel values at integer-coordinate positions taken from the index set Z x Z. We also assume that the relevant information of each image only comes from a square of size n pixels, outside which the pixel values are taken to be 0. We consider the application of single convolution kernel/filte, of k pixels (with & small odd number). One typically applies padding by layer of O's of size (k - 1)/2 on the perimeter of the which convolution with the kernel is computed on the n x n central pixels of the resulting (n + k 11) x (n + k 1) padded input image. The output relevant information is restricted to a n x n square, outside which pixel values are set to again, via padding.
square, after
Metric on X. As natural choice of distance over X' may consider 1,2ddiferencce between pixel-value functions, or interpret pixel values as probability densities, and use Wasserstein distance, consider other ad-hoc image metrics.
The group acting on our "pixel-value functions" is the group of translations with elements from & x Z. We expect the following invariance for the segmentation function J X - X:
Group action:
translations.
= f(x),
where x X' represents an image with pixel values assigned to integer coordinates and v E Z is a translation vector and (in two alternative notations) v x = (z(x) the result of translating all pixel values of x by
Deformation properties of the action. If we take the previously mentioned distance functions on X and the usual distance induced from I22 over translation vectors v, it easy to verify that the assumptions of Theorem A.3 about the action of translations hold, and the Lipschitz constants with respect to the metric on X' only depend on the mismatch near the boundary, due to "zero pixels moving in and to "interior pixels moving out" of our square, and being truncated. The ensuing bounds only depend on the precise distance that we introduce use on X.
More realistic actions. An alternative more realistic definition of Z x Z-action consists the truncation of (z) where, for pixels outside our "relevant"
of defining square we set pixel value to 0 after the translation.
Problems near the boundary. Nevertheless, the updated translation action, will move pixel values of 0, coming from pixels outside the n square, and will create artificial zero pixel values inside the image e x, different than the values that would be present real data.
Imperfect equivariance of data. Also, even in the latter more realistic alternative, the above translation equivariance is not respecting by segmentation input-output, pairs coming from finite n x n images, since, independently of n, the boundary pixel positions translated by v, fall outside the original image.
Approximate stabilizer. In any case, have to restrict the choices of to integer- coordinate elements of (subset of a) n square, containing only the translations that are relating "real" segmentations that appear within our relevant window. It is thus
22

---

natural to restrict Stab, to only include vectors in a smaller subset of Z x 2, of cardinality
Stab. S n².
The value of error may quantify the allowed error (or noisiness) for our model scts.
Reducing to finite G and computing x. For the sake of computing in our Theorem 6.1, we can observe that imput and output values outside the "padding perimeter" given by (n + 1) x (n + k ---1) 1) square, are irrelevant, and thus we may actually periodize the images and consider the images as subsets of a padded torus (Z/ (n + 1)2)², which we consider as acting on itself by translations. In this case G = (2/ k - 1))"" so that
G = (n + 1)² and thus A Stab.
(n + k: 1)2
Further extensions. In [27]. it is argued that convolutional layers in classical CNNs are not fully laanslatio-equuivaiiatte and can encode positional information, due to the manner in which boundary padding is implemented. Possible solutions are increasing the padding to size (so that the padded image is a square of size (n+ + 2k) x (n + 2k)) or extending images by periodicity, via so-called 'circular padding" (which transforms each image into space equivalent to the torus (Z/nZ)²). In either case, the application of actions by translations by vectors that are too large compared to the image size of will increase the mismatch between model equivariance and data equivariance.
Stride and downsampling. In [11]. a different equivariance error for classical CNNs is studied, related to the use stride outputs. If for example we use stride 2 when defining layer operation f X + V, then y will have relevant pixel values only an n1/2 n/2 n//asqqare, and we apply the k
order to lower the output dimensions of CNN layer
convolution kernel only at positions with coordinates in (2Z) (2Z) from image x. In this case require that translations by group elements a E (22) x (2ž) on æ have the effect of a translation by v/2 E E on the output. However for shifts in the input via vectors that do not have two even coordinates, we may not have have an explicit corresponding action on the output, and in [11] solution via adaptive polyphase sampling proposed. A possibility for studying the best polyphase sampling strategy via almost cquivariance, would be to include a bound for oquivariance crror <> 0 and consider the optimization problem of finding the polyphasc approximation that minimizes theoretical or empirical quantifications of e. As a benchmark (modelled on the case of infinite images without boundary effects) one could compare the above to the action via Stab, (2Z) x (2ž) which has = 1/4 within the ambient group G = Z Z. Our Theorem 6.1 can be used compare the effects of increasing or decreasing X, in terms of data symmetry.
B.2.2 Partial cquívariance in GCNNs
In this section, we connect the main results from [40] to setup. In [40], one of the main motivating examples was to consider rotations applied to a handwritten digit and revert them. The underlying group action was via S0(2) and only rotations of angles between [-60",60 60% were permitted one case, which allowed to not confound rotated digits "3" and "9" for example.
The above task can be formulated on a space of functions f: x in which X represents the space of possible images and y the labels. Elements (Ya, Yo) E y include digit classification label Yς and a rotation angle value Yg.
We consider actions by group G = SO(2) = (R.: OF R/360ZZ), where Rg is the rotation matrix by angle o, and the group operation corresponds to summing the angles, modulo 360 (or in radians, modulo 2x). The action of Rs over X' would be by rotation as usual ( Rg sends image x E X to Rg x, now rotated by 0), and over y we consider the action by
RYaYa, Yo) = (Ya, Yo +))
Le. the restriction of the action on the digit label leaves it invariant and the restriction of the action on the angle label is non-trivial, giving shift on the label.
23

---

The optimum labelling assigns to z a label y (æ) enjoying precise equivariance under the above definitions of the actions, and thus we are allowed to permit equivariance error 0. However as mentioned above, applying rotations outside the range 0 E [-60", 609) to the data would surely bring us outside the labelled data distribution, thus we are led to take
E ==
Stabo = {Ra= : 0 E -- 60")]
We then have that |Stabol/ [ = 1/3, with respect to the natural Haar measure rotations. It natural to think of the set of Stabo-action representatives of images 2 given as the 'unrotated' images. If we take a digit image that is rotated, say by 20', from its "base" version, and we apply a rotation of 50" to it (i.e. an element of Stabo), then we reach the version of the image now excessively rotated by 70%. This mcans that without further modification, considering model symmetrics with Staby taken to be independent of the point, would automatically generate some error when tested the data. While decreasing the threshold angle in the definition of Stabo from 60 would limit this effect, it will also decrease generalization error in the model. The study of point-dependent invariance sets Stab, is interesting in view of this example application, but it is outside the scope of the current approximation/geneeeee /generalizationn bounds and is left for future work.
B.2.3 Possible applications to partial cquivariance in Reinforcement Learning
The use approximate invariances for RL applications was considered in [23, Sec. 6] via soft equívariance constraints allowing better generalization for agent moving in geometric environment. While imposing approximate equivariance for memoryless G-action for groups such G 50()), Zz has produced positive results, it may be interesting, in analogy to the previous section, to include memory, and thus restrict the choices of group actions across time steps. Note that for a temporal evolution of T steps, the group action by G acting independently at each step would produce a T-interval action via the product group G² and allowing for a partial action via Stab,, with possibly increased filness evolving data. More precise time-dependence prescriptions and consequences within Q-learnig are left to future work.
C Discussion of [20]
In section 2 we mentioned [20]. which considers PAC-style bounds under model symmelry. [20] works with compact groups and argues how the learning problem in such a setup reduces to only working with a set of reduced orbit representatives, which leads to a generalization gain. This message of [20] is similar to ours, although we work with a more general setup, However, we noted that the main theorem in [20] has an error. Here, we briefly sketch the issuc with the proof.
One of the main quantitics of interest in the main thcorem of [20] is D, (XYYH H) (notation from their paper), which directly comes from the following bound, and is claimed to have linear dependence on Cov(X, 0), Again, for the sake of easier verification, we follow their notation. Crucially, note that [20) uses the notation Cov as analogous to N:
Cou(H, I 2C8 + K) I Cov(X, p, 0) sup Cov(H(x), (k,o,)) =Ex
However, the correct application of the reasoning in the proof should yield a dependence which is exponential in Cou(X, p, 5), not linear. To see this, set = 2 (sufficient for our purposes) in equation 238 in [54] (page 186).
Tikhomirov estimate shows that the
In other words, it is not possible to cover Lipschitz functions in infinily norm by only using constant functions.
24


Reviews:
[{"review_id": "0NJU9KJPtH", "reviewer": "Reviewer_CLQc", "summary": "There are two main results in this paper. The first one (Theorem 4.4) obtains a PAC-generalization bound for a hypothesis space which is approximately equivariant to transformations by elements g in G. This bound shows that in addition to the classical complexity term that depends upon the size of the hypothesis space, there are two additional terms that arise, one due to the approximate invariance (where one restricts to only the hypotheses that are equivariant to G) and another due to partial equivariance (where one relaxes the error to equivariance constraint). The proof of this result is classical (e.g., it is close to the Baxter’s proofs in “A Model of Inductive Bias Learning“).\n\nThe second result (Theorem 5.2) is about studying the interplay between equivariance imposed in the model and that possessed in the data. The key idea here is to construct a set of hypothesis spaces that capture a large subset of the \"symmetries\" in the data G, depending upon a parameter lambda; larger the lambda, smaller the set of hypotheses. This allows an upper bound on the approximation error in terms of lambda and the dimension of G.", "questions": "It would be useful to demonstrate a meaningful experiment (even if it is with synthetic data) where the three terms in Theorem 6.1 trade off against each other.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a thorough and pertinent paper that asks the question: how does the equivariance baked into the model relate to the inherent symmetries present in the data. This is a rare perspective. The proofs are somewhat straightforward but they are well-formulated and rigorous.", "weaknesses": "The writing in Section 5 can be improved a lot.\n\nI thought that the discussion in Theorem 6.1 could be done in a different way. Specific values of lambda and epsilon entail a choice of hypothesis space. The constant M in Theorem 6.1 therefore is smaller if lambda is larger (?).\n\nMinor\nI suspect the \\in S on line 251 is a typo.\ntilde cal F on line 289 and 298 should be just cal F I think.\ncal F’ on line 309 should be cal F.\nThere is clearly a typo on Line 310.\nC_G should be defined before Line 327.\nTheorem 6.1 should have n^{-1/2} for the first term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the very encouraging feedback. In particular, we are glad that our theoretical perspective on equivariance is appreciated and recognized to not have been commonly addressed. Thanks for the Baxter reference, which we were not aware of. \n\nBelow we will address some specific points raised in the review. \n\n### Writing in Section 5\nThank you for your constructive feedback. We acknowledge that our discussion is a bit compressed since we were pressed for space and we had a lot of material to cover. On acceptance, the additional page will provide us some more leeway to improve the discussion in general -- in the discussion section, around each result, and also for the limitations. For section 5, to improve the discussion, we will undertake the following actions. \n\n#### Actions\n- Provide some more intuition when we state the AppGap term and the three core assumptions.\n- Add some commentary on the model classes defined before Proposition 5.1. Cite some standard results for the isodiametric inequality.\n- Add a few lines below theorem 5.2 explaining its relevance.\n\nWe have worked on these additions, however, it seems like we are unable to submit a revised version of the paper during the rebuttal. Please let us know if you would like to see anything else added. \n\n### Discussion in Theorem 6.1\nThanks! This is an interesting suggestion. We think the discussion will certainly benefit by making it more explicit in the sense that you mention. We will add a few lines doing so. As a side note, we didn't quite follow the comment about \"constant M being smaller\", since it is fixed. Could the reviewer kindly clarify?\n\n### Typos\nThanks for catching it. We have fixed it and will propagate it when we are able. \n\n### Experiments\nIncluding some experiments supporting our main results is something that we considered quite seriously. Eventually, we decided against it for two main reasons: First, we thought that the results are really the first in formalizing and supporting a common intuition in equivariant learning -- a perspective that can be commonly found in introductory sections of equivariance papers , but without formal backing. We provide results on generalization and approximation errors for the general equivariant case and then combine them to tease out a trade-off. Existing works mostly only deal with generalization (not approximation, or the generalization and approximation tradeoff) and even for the exact group equivariance case, deal only with special cases. So we believe that our results are reasonable contributions by themselves.  Second, our results are very general and don't propose a specific prescription for equivariance/partial equivariance/approximate equivariance. If we provide experiments, they would amount to fixing a specific scheme for partial equivariance, so we eventually decided against it. However, to support our main result, we will consider some of the concrete cases we have described in the appendix e.g. in Finzi et al [1], cast it in terms of our main results and run some modified versions of the experiments they use in their paper. If accepted, we will consider adding an experiment such as this in the appendix and refer to it right after theorem 6.1. \n\nReferences mentioned in this response:\n\n[1] Marc Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equivariance constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 30037–30049. Curran Associates, Inc., 2021."}, {"review_id": "kLaf2hXLWS", "reviewer": "Reviewer_W1Je", "summary": "The submission discusses the role of task-specific symmetries in enhancing machine learning models. It presents a quantitative analysis substantiating the common intuition that task-specific symmetries lead to improved generalization. The authors delve into the interplay between model and data symmetry, particularly in the case of partial or approximate symmetries, establishing a defined link between model equivariance error and data equivariance error. They outline the conditions that lead to the optimal model equivariance error. However, the results are general and not model-specific, with the authors suggesting future research to formulate more specific versions of their theorem tailored to specific groups and neural network architectures.", "questions": "The paper's main contributions could be made more explicit. As it stands, the authors appear to enumerate their findings without adequately illustrating their novelty, importance, or applicability. Furthermore, the usage of numerous different notations creates some confusion; a table of notation might ameliorate this issue. While the paper seems to address a fundamental problem in machine learning theory, its presentation could be improved, and the clarity of its contributions could be enhanced.\n\nQuestions:\n\n1. The majority of results in the paper are upper bounds, but there is no discussion regarding their tightness. Could the authors elaborate on this aspect?\n\n2. In Lines 351-352, the authors mention that \"the above bounds are not informative.\" If the bounds lack informativeness, could the authors clarify the significance or utility of these results?", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "The paper provides a rigorous, quantitative exploration of task-specific symmetries in machine learning models.", "weaknesses": "The presentation of the paper's findings could be clearer, particularly with regard to illustrating their novelty and applicability, and the frequent use of different notations without a consolidated reference adds unnecessary complexity and potential confusion for readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time that you have taken to read our paper and for providing feedback. Below we will try to address some specific points that you have raised. \n\n### presentation \nAs we mentioned to reviewer CLQc, if accepted, we will use the additional page to add more context and discussion around the results. We have a set of results that don't really exist in the literature (except in special cases), and given the limited space, we had to affect our own trade-off in terms of presentation. We eventually decided to present our results taking the following approach: We have spent the first two pages to properly state the problem and prior work in intuitive terms. Then we have reviewed existing prior works and tried to state their contributions, we then specify what issues have not been considered in the literature. Then we provide some basic background for PAC style bounds, and then proceed to present some results step by step. We definitely agree that additional commentary could help the reader. If accepted, the additional page will help us do this, we can remove some parts and add more commentary before and after each result, and also discuss limitations in more detail. \n\n### novelty and applicability\nTo add to the point above. We would like to emphasize that results on generalization for equivariant models are quite limited. The first part of our work on generalization proves results that subsume many existing results even if we restrict our results to the strict equivariance case. However, our results can also work with partial/approximate equivariance, which is relevant in real-world applications, so they are quite more general. We then go further and also provide approximation error bounds and show how they can be combined together to work out a trade-off i.e. quantifying the effect of model misspecification -- when the model and data symmetries don't match. Let us know if we should improve the discussion around this. In the first 2.5 pages, we have tried to contextualize our work such that it is clear what its contributions are and how they are situated in the literature. At the end of the review of basic PAC bounds, we state 'we are now in a position to state our results', implying that all the results stated after that are new. \n\n### different notations without a consolidated reference\nThanks. We will add a consolidated reference table in the beginning of section 3. \n\n### Only upper bounds\nYes, we treat worst case results in the spirit of standard PAC style analysis. Stronger results that work for specific groups and under stronger structural hypothesis is an avenue that we are currently exploring. Although such results will still be upper bounds, but just sharper for specific use cases (groups, architectures).\n\n### Bound not informative\nWe believe that the reviewer might have misread this line. We will consider rewording it. In fact, we say that \"Note that the above bounds are not informative as $\\lambda \\to 0$ for the continuous group case, which corresponds to the second option in Theorem 6.1. This can be sourced back to the form of Assumption [...]\", what we mean is that the bounds in theorem 6.1 are not useful when $\\lambda$ is approaching zero, since the value of the upper bound tends to $\\infty$. We don't mean to imply that the bounds are not informative in general. Kindly let us know if we have misunderstood something. \n"}, {"review_id": "iepeoqqLrx", "reviewer": "Reviewer_y3sQ", "summary": "In their theoretic work, the  authors presents quantitative bounds on the generalization error and approximation error. They extend the results to approximate symmetries, which refers to functions that are close, in the supremum norm, to a group action.\n\nTheir first results shows that when working with only the representatives of $G$-Orbits, and the models are equivariant (or almost-equivariant) The generalization error can be nearly-recovered.  Their second results show that their exists a class almost-equivaraint estimators, such that its approximation error can be bounded (and the bound depends mostly on the properties of G, and somewhat on the pertubations of the optimal estimator).\n", "questions": "- Theorem 5.2 holds under the condition that there \\textbf{exists} $\\mathcal{F} \\in \\mathcal{C}_{\\varepsilon, \\lambda}$ such that the theorem holds. I am concerned that ideally, we would like it to apply to \\textbf{any} such $\\mathcal{F}$ . It would seem to me that it would align better with our original motivation as we would like to prove that any such partial symmetry family (with limited perturbation) can generalize well. I note that theorem 6.1 is under the same assumption so my question additionally applies to it\n-  I would appreciate further elaboration specifically on the interplay between model equavarince against data equavarince. How does the presented bound connect between them? can you show how further restriction of the models, choosing $\\mathcal{F}' \\subset \\mathcal{F}$ would affect the generalization and approximation bound.\n", "limitations": ".", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper is a novel and well presented work on approximate symmetry. The bounds presented are a significant contribution to the field, further deepening its theoretical foundations.\n", "weaknesses": "- The discussion section is lacking. It focuses on combining previous results and quantifying the lambda parameters. It is lacking interpretation of the results, and addressing your hypothesis. Under which conditions equivariance error is optimal? What is the interplay between data equivaraince to model equivariance? How does it compare to other bounds in the literature? \n- The limitation of this paper is not addressed properly. The authors only mentions that \"the results are not model specific\", which is not an actual limitation. It would be beneficial to discuss the actual limitation of the work. Can the bounds be computationally intractable? for example, how can one compute $ddim(G)$? What is the asymptotic growth of the presented bounds? \n    \n- The paper is lacking intuition into the $\\lambda$ parameter. Explanations are postponed into the discussion, and  even there, the interplay between $\\lambda$      and the error is drawn, but there is no attempt to demystify this parameter. I would appreciate further elaboration about it, and about the meaning of $Dens(\\epsilon)$. Is this the same as 'approximate orbits'$^{-1}$?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for a careful and critical reading of our paper and also for recognizing its significance in the literature on equivariance. \n\n### Discussion\nWe acknowledge that our presentation might appear a bit terse. As we mentioned to reviewer CLQc and W1Je, if accepted, we will use the additional page to add more context and discussion around each presented result. Since we were pressed for space, we took the following approach to presenting our results. We first spent the first two pages to give intuition about the problem and cover prior work in simplified terms. Then we review some basic PAC concepts and proceed to present our results step by step. We definitely agree that additional commentary could help the reader. If accepted, the additional page will help us do this, we can remove some parts and add more commentary before and after each result, and also discuss limitations in more detail. If you peruse our responses to other reviewers we have added more detail for additions. \n\n### Comparison to bounds in the literature\nIn the introduction and the related works section, we have tried to cover papers that present similar bounds and also briefly describe how they differ. After stating proposition 4.2, we point out below it, that it already generalizes existing bounds. The results after that are not directly comparable to existing work. \n\n### tractability and ddim\nCould the reviewer kindly clarify, \"computational tractability\" of what is being referred to? We would like the opportunity to clarify further. About $\\mathsf{ddim}(G)$, in the discussion around line 239 we briefly pointed out that for finite-dimensional Lie groups the doubling dimension corresponds to the usual dimension, which is known (these $G$ include rotation groups, Poincare groups, Euclidean isometry groups used in practice, or products thereof, amongst others). For more general $G$ the (polynomial/exponential) growth of groups is one of the main directions at the core of quite some deep work in Geometric Group Theory, which includes many answers in specific cases. However, the value for ddim will be known in most situations. We will be happy to add a remark about this in the extra space available, if accepted.\n\n### Asymptotic Bounds\nCould you clarify what limit are you thinking about when you talk about asymptotic growth? If clear to us, we are happy to include a discussion. \n\n### about results being model specific\nWe here expand on the ideas of why not being model specific is a limitation for our results. As mentioned in the response to referee R2KT, if we would include more model-specific discussions, this would allow more in-depth control of what can happen as we increase/decrease the amount of allowed symmetries, or the approximate symmetry threshold $\\epsilon$. To do this we would need to fix a model and to be specific about the action on the data and labels. Thus we decided against including this direction, with the motivation that it would have obscured the main interest of the paper, however we consider it a limitation because the description is less explicit. As a more precise example of this limitation, which we did not include due to space constraints, we note that for some classes of groups and actions, such as (products of) permutation groups acting on semantically equivalent token classes in language processing tasks, the bounds that we give using doubling dimension of the groups can be improved, using the specific form of the symmetry group and action in that case. In fact this seems to be a very interesting avenue of research, which we are currently exploring.\n\nWe will consider expanding on these points, if accepted. \n\nWe additionally will discuss more limitations, starting with the assumptions. For instance, our results require that the group under consideration has certain doubling properties which hold for groups such as locally compact groups. To prove analogous results as in our paper, for permutation groups, would require different analysis. This is an avenue for future work as it would involve understanding and relating the metric properties of permutation groups to the kind of concentration results that we use. \n\n### Lambda parameter\nThank you for pointing this out. We will add to our discussion around $\\lambda$ if the paper is accepted. This parameter determines how many of the allowed symmetries (i.e. what percentage of the group $G$) are actual symmetries of our model class. The main intuition is that if $\\lambda$ becomes smaller, in terms of class of model classes $\\mathcal C_{\\epsilon,\\lambda}$ this means that we are relaxing the symmetry requirement on the model classes $\\mathcal F$, thus the models in such $\\mathcal F$ become more free to adapt to the data distribution. This increase of $\\lambda$ describes what is usually called \"partial equivariance\" in the literature. On the other hand $\\epsilon$ has the role of allowed error in the allowed symmetries (allowing so-called \"approximate equivariance\" in the models). \n\n### Q1\nPlease see above part on \"lambda parameter\". Also see our response to reviewers R2KT (under \"explicit symmetry\") and PxmR (under \"tradeoffs\"), since we seem to have run out of space in our rebuttal.\n\n### Q2\nPlease see above part on \"lambda parameter\". \nSecond part of second question: We would appreciate if the reviewer could clarify what kind of restrictions in passing from $\\mathcal F$ to $\\mathcal F'$ the reviewer has in mind. Depending on this, the answer can be quite involved. If the restrictions are of the type of restricting the approximate equivariance error or making \"less partial\" the partial equivariance constraint (by increasing $\\lambda$) then the relation is direct from the discussion after Thm. 6.1, which however we plan to explain in the appendix, if the paper gets accepted, in order to make it more explicit. If the referee intended something else, then we would be grateful if they can specify the question in more detail."}, {"review_id": "5QgZKnRb6N", "reviewer": "Reviewer_R2KT", "summary": "This paper provides theoretical investigation on the intuition that, machine learning models (e.g. neural networks) whose symmetry aligns with the data symmetry achieve best performance and generalization. The paper formulate the relationship between model equivariance error and data equivariance error by providing quantitative bounds, which are applicable in the presence of approximate or partial data/model equivariance.", "questions": "1. More regarding the interpretation of the \"generalization-approximation trade-off\"/\"optimal equivariance\":\n\n    If we examine the contribution of $\\lambda$ to the generalization and approximation bounds given by Theorem 4.4 and 5.2 respectively, assuming perfect symmetry of data ($\\epsilon=0$), we see that the former decreases when $\\lambda$ increases ($\\frac{1}{\\lambda^{1/2}}$ or $\\frac{1}{\\lambda^{1/d_0}}$ scaling), while the latter increases when when $\\lambda$ increases ($\\lambda^{1/d_G}$ scaling), which gives what the authors called \"generalization-approximation trade-off\". To me, this seems to show that minimizing the generalization error effectively aligns the model and data symmetries, whereas minimizing the approximation error functions in the opposite direction, resulting in a partially aligned model symmetry. \n\n    Do you agree with this analysis? Any further explanation/intuition?\n\n2. Can you explain what you mean by \"oscillations\", which is mentioned repeatedly? Example contexts like:\n\n- \"since $\\text{Stab}_{\\epsilon}$ includes more elements of G as ε increases, and we can expect that actions of elements generating higher equivariance error in general have higher oscillations\". (line 274-275)\n\n- line 320-322", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. To my best knowledge, the paper provides a systematic and comprehensive review of the historical development of neural networks with group symmetries (**since this is not exactly my area of research, please correct me if I'm wrong**).\n\n2. The paper provides detailed and systematic analyses of the model generalization bounds as well as approximation bounds under the more general case of partial or approximate equivariance. According to the authors, as well as to my best knowledge, this is the first theoretical work that addresses this problem. Therefore its contribution and novelty is significant.\n\n3. Although not being able to check every technical details and derivations, I find the paper well-structured and easy to follow.", "weaknesses": "**Major issues:**\n\n1. Derivation of the approximation error bounds:\n\n- First of all, in line 291, I don't think it's legal to write $\\min A - \\min B$ as $\\min(A-B)$, since the second term has a minus sign. So I think the correct way to write is that\n\n    $\\text{AppGap}(\\mathcal{F}, \\mathcal{D}) := \\underset{f\\in\\mathcal{F}}{\\min}\\mathbb{E}[\\mathbb{E}_g[f(g\\cdot Z)]] - \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[F(Z)] \\ge \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[\\mathbb{E}_g[F(g\\cdot Z)]] - \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[F(Z)] $\n\n- The expression above provides a **lower bound** to the approximation gap, so how does the inequality become equality in Line 304? If it is derived by assuming $\\mathcal{F} = (\\mathcal{M}^{(G)})'$ (assumption 3 in line 301=303), then line 304 should be written as\n\n    $\\text{AppGap}((\\mathcal{M}^{(G)})',\\mathcal{D}) = \\underset{F\\in(\\mathcal{M}^{(G)})'}{\\min}\\mathbb{E}_Z[\\mathbb{E}_g[F(g\\cdot Z)]]$\n\n- Moreover, if the upperbound in Prop 5.1. is derived based on the equation above, I think it's necessary to prove that $(\\mathcal{M}^{(G)})'\\subseteq \\mathcal{C}_{\\epsilon,\\lambda}$ , for any $\\epsilon\\ge 0, \\lambda\\in(0, 1]$, which I don't see in the proof.\n\n2. Interpretation of the \"generalization-approximation trade-off\"/\"optimal equivariance\" is not clear:\n\n    In line 360-362, it is claimed that the optimal $\\lambda^*$ \"validates the intuition stated at the onset that for the best model its symmetries must align with that of the data\". However, based on my understanding, the symmetries of the model **only fully align with those of the data** when $\\lambda^*=1$, given $\\epsilon=0$. When $0<\\lambda^*<1$, I think it means the model only **partially preserves the symmetries of the data**. Do you agree? If this is the case, how do you justify the intuition that \"the integration of relevant symmetry results in enhanced generalization.\"?\n\n3. Similar to reference 9 in the paper, I think one key point I would expect to see in this paper is proving that, models with aligned group symmetries of data exhibit higher sample efficiency/complexity, which can generalize to scenarios of partial/approximate symmetry. I see no discussion or proofs regarding this intuition in the paper.\n\n  **I will be happy to raise my score given satisfactory explanation or revision.**\n\n**Minor Issues:**\n\n1. This paper targets specifically on the theory of machine learning models with partial/approximate group symmetries, which might be of interests only to a very specific subgroup of the whole machine learning community.\n\n2. There are some presentation issues need to be improved:\n\n    - All hyperlinks do not work when clicked. Some numberings are also confusing, e.g. what is Thm A.4 in line 242, 246, 268?\n\n    - Some of the statements would benefit from more citations/examples, e.g.\n     \"It has often been noted that this may impose an overly stringent constraint as real-world data seldom exhibits perfect symmetry” (line 36 - 37)\n3. Typos\n\n    - may have not -> may not have (line 312)\n\n    - $\\text{Stab}{\\epsilon}(\\mathcal{F'}) \\Longrightarrow \\text{Stab}{\\epsilon}(\\mathcal{F})$ (line 309)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very encouraging comments on our work. We are grateful that you appreciate its significance and novelty and that you also liked our treatment/survey of the historical results in the area. :) We also found your questions instructive, and acknowledge their role in improving our presentation. We address each of the points raised below.\n\n### Derivation of approximation error bounds\nThis is a good catch. This was an oversight while presenting our results, and you are right that we have a wrong step in our derivation, as $ \\min{A} - \\min{B} \\geq \\min(A-B)$ and equality is not true in general. Thank you for pointing this out. Here is our response to this. For the replacement in our proofs, as mentioned in your report we can start with: \n\n$ \\text{AppGap}(\\mathcal{F}, \\mathcal{D}) \\ge \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[\\mathbb{E}_g[F(g \\cdot Z)]] - \\underset{F\\in\\mathcal{M'}}{\\min} \\mathbb{E}[F(Z)] (1). $\n\nFrom this point onwards, we can select $F^*$ which realizes the first minimum, and then we have:\n$\\mathbb{E}[\\mathbb{E}_g[F^*(g\\cdot Z)]] = \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[\\mathbb{E}_g[F(g\\cdot Z)]]$ and $  - \\underset{F\\in\\mathcal{M'}}{\\min} \\mathbb{E}[F(Z)] \\ge - \\mathbb{E}[F^*(Z)].$\n\nSumming last two inequalities: $ \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[\\mathbb{E}_g[F(g\\cdot Z)]] - \\underset{F\\in\\mathcal{M'}}{\\min} \\mathbb{E}[F(Z)] \\ge \\mathbb{E}[\\mathbb{E}_g[F^*(g\\cdot Z)]] - \\mathbb{E}[F^*(Z)].$\n\nNow the term on the right in the last inequality is a competitor for the minimization $\\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb E[\\mathbb{E}_g[F(g\\cdot Z)] - F(Z)],$ and we find $(1)\\geq \\underset{F\\in\\mathcal{M'}}{\\min}\\mathbb{E}[\\mathbb{E}_g[F(g\\cdot Z)] - F(Z)], $ as appears in our paper.\n\n### inequality/equality\nWhat the referee writes is true, but line 304 in the paper is also correct. Note that we also have that $F\\in(\\mathcal M^{(G)})'$ is equivalent to $F(Z)=\\mathbb E_g[F(g\\cdot Z)]$ for all $Z$. Consequently, symmetrization map $F\\mapsto [Z\\mapsto\\mathbb E_g[F(g\\cdot Z)]$ is an involution from $\\mathcal M'$ onto $(\\mathcal M^{(G)})'$ and in particular all measurable invariant functions are all obtained by symmetrization:\n$(\\mathcal M^{(G)})'=\\{Z\\mapsto\\mathbb E_g[F(g\\cdot Z)]:\\ F\\in \\mathcal M'\\}.$\nThus, starting with the formula written by the referee, we also get\n$\\min_{F\\in (\\mathcal M^{(G)})'}\\mathbb E_Z[\\mathbb E_g[F(g\\cdot Z)]] = \\min_{F\\in \\mathcal M'}\\mathbb E_Z[\\mathbb E_g[F(g\\cdot Z)]]=\\mathsf{AppErr}(\\mathcal F,\\mathcal D),$\nwhich is the formula claimed in the paper.\n\n### upper bound/5.1:\nAssuming the above response to point 2 is satisfactory, the point raised by the referee after that \"if the upper bound in Prop 5.1 is derived based on the equation above\" (meaning, \"based on the equation of point 2\") should be automatically be resolved. \n\n### optimal $\\lambda^*$\nIndeed, in our formulation $\\epsilon$ controls the allowed error in equivariance and $\\lambda$ controls the proportion of elements of the group which are included in the computation of this error, thus measures the amount of symmetry included in the models. If we set $\\epsilon=0$ then the minimum $\\lambda^*$ for the error bound estimate from our theorem 6.1, indicates a value for the optimal proportion of group elements to be included in $\\mathsf{Stab}_\\epsilon$, i.e. for the measure of allowed symmetries in the models. If we take $\\lambda>\\lambda^*$ or $\\lambda< \\lambda^*$ this will worsen the error bounds, indicating that there exists a \"precise quantity of symmetries\" that one needs to include in the model for optimality: adding symmetries which would increase error because they are not present in the data, and adding too few symmetries will worsen generalization improvement and lead to higher error.\n\n### explicit symmetry\nThe reason for not including such explicit symmetry comparison in our proofs is that we focus on a higher generality than the one of reference [9] indicated above: we do not make strong assumptions on the groups or of the type of symmetries of the data. Thus we prove our bounds with minimal assumptions. An explicit comparison of model versus data symmetries would have increased the length and changed the focus of the paper, without deep changes in the fundamental concepts. We can include the following discussion in the additional space allowed for the final version of the paper, if accepted.\n\nFor the precise comparison, we start by recalling that, roughly speaking, in Sections 4 and 5 respectively, we prove that \n\n(Sec. 4) If we allow a rich enough set of approximate symmetries of the model $\\mathsf{Stab}_\\epsilon$, we get better generalization bounds. Note that this part is valid for any data distribution, it does not require assumptions on symmetries of the data so far.\n\n(Sec. 5) If we wish to have small approx error, we need to allow freedom on the amount of symmetries. This is measured by $\\lambda$ which bounds the size of the stabilizer $\\mathsf{Stab}_\\epsilon$$ relative to the full group $G$. The approx error also includes a dependence on the error in our symmetries, measured by $\\epsilon$. Note that for the approx error bound we still do not fix any explicit symmetry properties for the data, therefore rather than proving a result valid for all models in class $\\mathcal{C}_{\\epsilon,\\lambda} $, we guarantee the existence of at least one efficient model in this class. The underlying idea is that for an optimal model its symmetries will necessarily fit to those of the data (since we guarantee that this model class will approximate well the data). Therefore, our approximation bounds imply that, independently of the data symmetries, the improvement due to \"symmetry alignment\" is bounded as in Theorem 5.2. \n\nIn future work it will be interesting to fix a specific class of symmetry groups; fix a quantification for the amount of symmetries present in data; make the approximation error dependence explicit, therefore making Theorem 5.2 more explicit."}, {"review_id": "dDmpbRyxhY", "reviewer": "Reviewer_5syP", "summary": "In this paper, the authors spell out explicitly the benefit of capturing task specific symmetries into machine learning models. This goal is achieved by deriving rigorously  generalization error bounds that takes into account the cardinality of the set of transformations that a model is (approxaimately) equivariant to (Stab_\\epsilon) as well as the group dimensionality these transformations are elements in.\nThe results are very general and unlike previously presented results in the literature, the sets of transformation the model is equivariant to, are not required to form a group.", "questions": "Is there anything that can be said about the tightness of the presented bounds?\n", "limitations": "The authors state that the derived bounds are not model specific and stronger versions could be the subject of future work. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presented approach to derive the bounds is principled and very interesting.   \n", "weaknesses": "While the derived results are very general and rigorous, it is not directly obvious how these results can be applied. Although the authors give examples in the appendix, the impact of these bounds seems relatively limited. It could have been maybe useful to show an actual model performance w.r.t. the presented bound.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciative comments about our work and recognizing its contribution to the literature. We hope to address some of the questions raised point-by-point below.\n\n### Applicability and experiments evaluation\nAs we mentioned to reviewer CLQc, we have considered including experiments quite seriously. However, since this is the first paper to address the tradeoff between generalization and approximation in a general equivariant setting, we feel that its role is to establish intuition and establish the important principles at work. Note that existing works mostly only deal with generalization, only with precise equivariance, and in that restriction, only with special cases. However in most real-life cases, we do not have neither full nor precise symmetry: the value of our paper is to see how to fit this in theoretical estimates. Further, our results cover a full range of generality, we have the weakest available assumptions on the form of the action of the symmetry group on the involved spaces. In particular note that there is no classification of the types of actions that might occur. As mentioned in the response to reviewer CLQc, if required we may implement modified versions of the experiments of reference [1], and consider adding these experiments comparing them to Theorem 6.1.\n\n### Q1 tightness of upper bounds\nAlso see our response to reviewer W1Je. Indeed, as in standard PAC theory, we prove upper bounds independent on the data distribution. The insight in the proofs is that we rigorously illustrate the interplay/tradeoff between approximation and generalization bounds in the setting of equivariance. To prove tightness of the bounds we would have to build problematic data distributions, and show that the PAC bounds worst case scenario is sharp. This is not done in PAC theory, and we did not pursue it here, the motivations being that the so-constructed datasets would require very technical, abstract and lengthy constructions and would likely be unrealistic. Thus they would shed very limited (if any) light on phenomena that can be useful for applications. We are currently exploring stronger results that work for specific groups and under stronger structural hypothesis. But such results will still be upper bounds, but just sharper for specific use cases. The bounds can also be improved in other ways, such as being made data-dependent. \n\nReferences used in this comment:\n\n[1] Marc Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equivariance constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 30037–30049. "}, {"review_id": "dh6ziYTKYo", "reviewer": "Reviewer_PxmR", "summary": "The paper presents a theoretical investigation into the approximation and generalization errors for a model exhibiting approximate equivariance. The paper introduces the concept of \"error to equivariance,\" a measure of the deviation of the error function from perfect equivariance. It then defines the $\\epsilon$-stabilizer, a subset of a group under whose transformations the error function maintains approximate equivariance. Leveraging these definitions, the paper dives into the analysis of generalization error for an approximately equivariant model in terms of PAC-bounds and Rademacher complexity, after which, It also explores the approximation error. Ultimately, the performance error of a model is defined as the sum of its generalization error and approximation error, providing a quantitative measure of the performance of an approximate equivariant model. In the end, the performance error can quantitatively analyze the trade-off between its two terms (generalization error and approximation error).", "questions": "1. Could the authors comment on the broader implications of the proposed theory? Specifically, could the theory help model selection under approximate equivariance? \n2. The paper is titled \"Approximation-Generalization Trade-offs\", however, the high-level message regarding this trade-off isn't clear. \n3. In line 140, there is a closing parenthesis but no opening parenthesis.", "limitations": "The paper properly discusses its limitations. An additional limitation to consider is the assumptions of the paper. The paper makes a couple of assumptions throughout the theoretical analysis, it might be good to summarize and discuss those assumptions in the limitation section. ", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper theoretically studies approximate equivariance, which is a very significant problem in the equivariant learning literature as real-world problems are not always perfectly equivariant. \n2. The paper provides general bounds, contributing valuable theoretical tools to the field.", "weaknesses": "1. Section 4 is somewhat challenging to read, especially for readers who are not familiar with PAC-bounds and Rademacher complexity. Additional explanations or intuitive examples could improve accessibility.\n2. While not a requirement for a theory paper, the absence of empirical validation or experiments leaves a gap. Experiments that align with the theoretical bounds could provide practical guidance on how the paper's findings might be applied empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very encouraging feedback and recognizing the importance of our work. We try to address each of the points raised one by one below:\n\n### Section 4 \nThanks for pointing out that accessibility could be improved! Since section 4 mostly describes background, we decided to compress it a little bit due to space constraints and get more space for newer results. To address this, we can add a refresher section in the appendix. If the reviewer has other instructions, we would be glad to consider them for incorporation. \n\n### Empirical Validation. \nAs we also mentioned to reviewers CLQc and 5syP, we thought seriously about including some experiments. However, we eventually took a call to not include experiments due to a couple of main reasons. First, the results that we present are really the first in formally presenting a common perspective in equivariant learning -- which is often stated in introductory sections -- but hasn't quite been formalized. We provide results for both generalization and approximation errors for the general case when the symmetries need not form a group, and then use them to work out a tradeoff which quantifies the effect of model misspecification. In fact, even if we consider only generalization bounds, existing results are limited to exact equivariance, and even there deal with special cases. Given that we go a few steps further for generalization, and then add results on approximation as well, we thought our results might be sufficient enough for a standalone contribution. Second, a flipside of the generality of our results is that they don't propose a specific prescription for equivariance/partial equivariance/approximate equivariance. If we provide experiments, they would amount to fixing a specific scheme for partial equivariance, so we eventually decided against it. However, to support our main result, we could consider some of the concrete cases we have described in the appendix e.g. in Finzi et al [1], cast it in terms of our main results (which we had explored while writing the paper) and run some modified versions of the experiments they use in their paper. If accepted, we will consider adding an experiment such as this in the appendix and refer to it right after theorem 6.1. \n\n### Model selection\nWe will add some comments on this. Since we do a PAC-style analysis, and the models we treat are quite general, the guidance is somewhat weak. However, if we fix stronger structural hypothesis to obtain the equivalent of theorem 6.1 in specific settings, we could get more tangible directions for model selection. This is an avenue that we are currently exploring. We will add some comments on this in \"limitations\", if accepted.\n\n### Tradeoffs\nWe will be sure to be more clear about the high-level message about this tradeoff i.e. the effect of model misspecification both in the beginning and end of the paper. However, just to reiterate: In section 4 of the paper we basically show that if we allow a reasonably rich set of approximate symmetries of the model, we get better generalization. Note that this part holds for any data distribution and makes no assumptions about the symmetries of the data. In section 5, we look at the approximation error. If we wish to have small approximation error, we need to permit more freedom on the symmetries. We measure this by the parameter $\\lambda$ which bounds the size of the stabilizer $\\mathsf{Stab}_\\epsilon$ relative to the full group $G$. The approximation error also includes a dependence on the error in our symmetries, measured by $\\epsilon$. However, even here, we we still do not fix any explicit symmetry properties for the data. This implies that we can guarantee that there exists at least one efficient model efficient model such that its symmetries will necessarily fit to those of the data. Thus, our theorem 5.2 implies that independent of data symmetries, the improvement that we see due to \"symmetry alignment\" is bounded. When we combine both results in theorem 6.1, this tradeoff becomes more explicit. We can definitely add more comments to make it more explicit. Let us know if you would have specific guidance on what you would like to see with regards to your question. \n\n### Typos\nThanks for pointing these out -- we have fixed them. \n\n### Limitations\nThanks for the suggestion! We will also list our assumptions in the limitations section. Some of these might also be more interesting for future work. For instance, our bounds work well for groups that are nicely doubling e.g. locally compact groups, but making them work for permutation groups requires more careful analysis since their metric structure is not easy to treat in the same manner as we use in our paper. \n\n\nReferences cited in this comment:\n\nReferences: [1] Marc Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equivariance constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 30037–30049.\n"}]

Author rebuttal:

Meta-review: The paper is aimed at contributing to a growing body of work investigating the performance of ML models under various relaxed notions of symmetry. Central to the analysis is $Stab_\epsilon$, a notion relaxing the conventional form of group stabilizers allowing $\epsilon$-error. Classical results from statistical learning theory are used together with the latter to derive generalization and approximation bounds, and trade-off thereof. 

The reviewers appreciated the problem the paper sets to address and found the bounds resulting by the use of $Stab_\epsilon$ enabling a more quantitative, if theoretical, exploration of the total error under relaxed symmetry, novel and intriguing. The authors are encouraged to incorporate the important feedback given by the knowledgeable reviewers (also make sure the correct NeurIPS format is used).
Decision: Accept (poster)