Generalization Bounds for Canonicalization: A Comparative Study with Group Averaging
Authors: Behrooz Tahmasebi
Stefanie Jegelka
Venue: ICLR 2025 Poster (2025)
Keywords: invariances
group
symmetry
canonicalization
Primary area: learning theory
TL;DR: We investigate generalization bounds for canonicalization and provide a comparative analysis with group averaging.

Abstract: Canonicalization, a popular method for generating invariant or equivariant function classes from arbitrary function sets, involves initial data projection onto a reduced input space subset, followed by applying any learning method to the projected dataset. Despite recent research on the expressive power and continuity of functions represented by canonicalization, its generalization capabilities remain less explored. This paper addresses this gap by theoretically examining the generalization benefits and sample complexity of canonicalization, comparing them with group averaging, another popular technique for creating invariant or equivariant function classes. 
Our findings reveal two distinct regimes where canonicalization may outperform or underperform compared to group averaging, with precise quantification of this phase transition in terms of sample size, group action characteristics, and a newly introduced concept of alignment.
To the best of our knowledge, this study represents the first theoretical exploration of such behavior, offering insights into the relative effectiveness of canonicalization and group averaging under varying conditions.

Published as a conference paper at ICLR 2025
GENERALIZATION BOUNDS FOR CANONICALIZATION: A COMPARATIVE STUDY WITH GROUP AVERAGING
Behrooz Tahmasebi MIT
Stefanie Jegelka TUM and MIT
ezt t edu
ABSTRACT
Canonicalization, a popular method for generating invariant or equivariant function classes from arbitrary function sets, involves initial data projection onto reduced input space subset, followed by applying any learning method to the projected dataset. Despite recent research on the expressive power and continuity of functions represented by canonicalization, its generalization capabilities remain less explored. This paper addresses this gap by theoretically examining the generalization benefits and sample complexity of canonicalization, comparing them with group averaging, another popular technique for creating invariant or equivariant function classes. Our findings reveal two distinct regimes where canonicalization may outperform or underperform compared to group averaging, with precise quantification this phase transition in terms of sample size, group action characteristics, and a newly introduced concept of alignment. To the best of our knowledge, this study represents the first theoretical exploration of such behavior, offering insights into the relative effectiveness canonicalization and group averaging under varying conditions.
INTRODUCTION
The goal of learning with invariances is to leverage known symmetries present in data to build models that are inherently invariant. Such symmetries frequently arise various machine learning applications, particularly in the natural sciences (see, e.g., (Batzner et al., 2022; Grisafi et al., 2018; Unke et al., 2021)). Examples include Euclidean symmetries and equivariances (Smidt, 2021) 1), among others. These forms of invariance are collectively addressed within the broader framework of geometric deep learning (Bronstein et al., 2017).
Several approaches are available for embedding invariances into machine learning models, including designing models with built-in invariance tailored to specific applications. Notable examples include Graph Neural Networks (GNNs) for graph data (Scarselli et al., 2008; Xu et al., 2019a), Convolutional Neural Networks (CNNs) for image data (Li et al., 2021; Krizhevsky et al., 2012), and PointNet for point clouds (Qi et al., 201 7a:b). These methods rely tailoring the network architecture to the particular type of invariance relevant to the application.
Another common approach introducing invariances is with additional modules to ensure the final representation invariant with respect to any group. Techniques in this category include group averaging (Murphy et al., 2019), frame averaging (Puny et al., 2022), and canonicalization (Kaba et al., 2023), the latter of which forms the central focus of this paper.
base function class and augment
In canonicalization. the data is first mapped onto lower-dimensional space to reduce redundancies arising from inherent invariances. transformed data (see Figure 2). This contrasts with group averaging, where the model is trained such that its output, averaged over all group transformations of the data, is plausible.
model, such as a neural network, then trained on this
Given the empirical success of these methods for learning under invariance, there has been significant interest in understanding their theoretical foundations, particularly in terms of expressive power
'EECS and CSAIL.
CTT, MCML,, and MDSI.

---

Published as a conference paper at ICLR 2025
Generalization Error
Canonicalization (CAN)
Group Averaging (GA)
CAN outperforms
GA outperforms
k
Samples
Neritical
Figure 1: When 2 Neritical, canonicalization demonstrates superior performance group averaging in terms of generalization eπтоr (sample complexity). In this scenario, the optimal target function I aligns with the canonicalization scheme (3 Conversely, when S Neritical, group averaging is preferred as it provides a smoother approach to constructing invariant functions.
and benefits like sample complexity and generalization bounds. For example, has been shown that group averaging enables strong generalization, allowing models to learn effectively with much smaller sample sizes compared to cases without invariance. However, much less is known about the theoretical properties of canonicalization.
In this paper, we aim to address the gap in understanding the generalization properties of canon- icalization by studying it compared group averaging, which serves baseline. This joint analysis reveals the strengths of both approaches and provides a theoretical basis for their comparison.
Specifically, we seek answer the following question:
Under what conditions do canonicalized models generalize well, and when do they outperform group averaging?
To this end, introduce the concept of alignment. A target function is said be aligned with canonicalization scheme it can be well-approximated by end-to-end canonicalized representations derived from "simple" base functions. This idea is inspired by algorithmic alignment (Xu al., 2019b), which was developed to explain the generalization capabilities of Graph Neural Networks (GNNs) by demonstrating that they produce functions aligned with dynamic programming-like distributed algorithms on graphs. Furthermore, prior work has shown that learned canonicalization can be highly effective in various applications (Kaba al., 2023). This paper provides theoretical foundation for understanding how learned canonicalization may outperform group averaging when canonicalization is more aligned with the downstream task.
In particular, we identify phase transition when comparing the generalization performance of canonicalization and group averaging (Figure 1). Specifically, if the number of samples available to the learning algorithm is below critical threshold, denoted Naritical, group averaging exhibits superior performance. Conversely, when the number of samples exceeds Naritical, canonicalization has the potential to outperform group averaging, provided the canonicalized model is well-aligned with the target function (Definition 2). The improvement offered by canonicalization such cases grow arbitrarily large the alignment with the target task increases. Furthermore, derive
2

---

Published as a conference paper at ICLR 2025
complete characterization of Neritical function of the properties of the group and the underlying function space.
To the best of our knowledge, this is the first theoretical investigation into this behavior, offering new insights into the comparative effectiveness of canonicalization and group averaging under different conditions.
In summary, this paper makes the following contributions:
We analyze the generalization bounds and sample complexity advantages of learning with canonicalized models.
We conduct a comparative theoretical study with group averaging to identify when canoni- calization can outperform group averaging in terms of sample complexity.
We introduce the notion of aligument for canonicalized models and demonstrate that the superiority of canonicalization or group averaging depends on whether the target task aligns with the canonicalization scheme. To our knowledge, this is the first detailed exploration of this behavior for both canonicalization and group averaging.
RELATED WORK
Euclidean symmetry and equivariance have garnered significant recent interest in machine learning applications (Smidt, 2021; Bronstein al., 2017), although their study dates back earlier works (Hinton, 1987; Batzner et al., 2023). These concepts have led to numerous approaches for incor- porating symmetry into machine learning models, including techniques such group averaging (Murphy et al., 2019), frame averaging (Puny et al., 2022), canonicalization (Kaba et al., 2023; Ma al., 2024a; Panigrahi Mondal, 2024), and random projections (Dym & Gortler, 2024). is worth noting that canonicalization can face challenges related to discontinuities and stability issues (Dym al., 2024).
Moreover, the study of invariances extends beyond learning; recent works have explored learning invariances neural networks (Benton et al., 2020), measuring invariances (Goodfellow et al., 2009), and optimization approaches that account for invariances (Teo et al., 2007); see also (Bloem-Redd) et al., 2020; Chaimanowong & Zhu, 2024). Specific applications of canonicalization, particularly for sign and basis invariances, have also been recently proposed (Lim al., 2023; 2024), with related work on Laplacian baaseeda---aeedd approaches (Ma et al., 2024b).
Consequently, the generalization capabilities of invariant classifiers have attracted significant atten- tion in recent years (Sokolic et al., 2017). For learning with kernels (Scholkopf & Smola, 2018), several studies have explored group averaging develop kernel methods for handling invariances, investigating its generalization error (Tahmasebi & Jegelka, 2023; Bietti et al., 2021; Elesedy, 2021; Mei al., 2021).
For equivariance, numerous approaches have also been proposed, such as parameter sharing (Ravan- bakhsh al., 2017), with various works examining its generalization properties (Petrache & Trivedi, 2023; Behboodi et al., 2022; Elesedy & Zaidi, 2021). Incorporating equivariances in sampling for generative models has likewise been shown to beneficial (Biloš Günnemann, 2021; Köhler et al., 2020; Niu et al., 2020). Furthermore, recent work has explored the complexity of learning under invariances for gradient-based algorithms (Kiani et al., 2024).
PROBLEM STATEMENT
We consider classical learning setup with a dataset of n labeled examples, S ((x,, ((r,,y)) y.) E [m]]. where the inputs K,, i [n], are i.i.d. samples from a uniform distribution over the manifold input space X' C Rd. The labels generated by unknown continuous target function f*, such that y: = f* (2,) c where the noise terms e,, for E [n], are independent, zero-mean random variables with variance bounded by の² The objective is to learn f" from the data.
3

---

Published as a conference paper at ICLR 2025
2 E X
f E F
f(+())
Figure 2: Canonicalization for creating invariant function classes.
Empirical Risk Minimization (ERM) provides estimator for this problem through the following optimization program:
min Σ (f())))))
JEF REIM
where ((:-) denotes squared loss, and represents the function class from which is selected.
3.1 LEARNING WITH INVARIANCES
In the context learning with invariances, the optimal target function f is invariant under the continuous action of a group G on the input space X' This means that for all E X and E G, the functional equation f* (gxx) = fxx) holds. Here, gr denotes the transformation of the element E X' under the action of the group element G. For simplicity, we assume throughout this paper that finite.
Note that the invariance of I' does not necessarily imply that the ERM solution is an invariant estimator. To leverage these invariances in the learning process, various methods can be employed, such as group averaging, canonicalization, data augmentation, and frame averaging. In this paper, we focus on the first two methods and provide brief review of these approaches in the following subsections.
3.2 GROUP AVERAGING
Group averaging is a method for obtaining invariant functions from set of base functions F. The idea that given an arbitrary function f F, the function R[f), defined as
R()(2) = 1 f(x),
BEG
invariant with respect to the group G. Here, R[-] is sometimes referred to the Reynolds operator corresponding to the group G. Given a function space F, let us denote the space of functions represented via group averaging as FGA which is formally defined follows:
FGA = R(f)
(3)
3.3 CANONICALIZATION
Canonicalization provides an alternative approach to constructing invariant function classes. Let X X/G denote the quotient space of the action of G on X, formally defined as X/G == ([x) : X). where [x] == {gr: E G} represents the orbits of the group. We assume X' X/G is embedded in the input space X, meaning X X/G X. The embedding (or projection) map π X' + X/G maps elements from the input space to their representation in the canonicalized space X' X/G.
Figure illustrates how canonicalized function classes are constructed from set of base functions E F. In canonicalized models, any E X' is first mapped to the canonicalized (or quotient) space through the projection function и. The projected data 7 ((x) is then passed to a base function F. yielding the final output (T))). The set of all canonicalized functions is defined as:
FCAN = [(((()): SEF).
(4)
4

---

Published as a conference paper at ICLR 2025
3.4 SETUP AND ASSUMPTIONS
As discussed, in learning with invariances, we begin with base function class F and then employ a method construet invariant function classes, such as group averaging FGA or canonicalization empirical risk minimization (ERM) over the new
FCAN. We then formulate the problem invariant function class to achieve an invariant estimator.
It is well known that both function classes FGA and FCAN are universally expressive: under mild conditions on the set base functions F. both function spaces can approximate any invariant and continuous function. However, universal expressiveness is not sufficient to ensure learnability. While expressiveness concerns to the ability of the new function class to approximate any continuous function, learnability concerns whether algorithm (such as ERM) can learn the target function with appropriate sample and computational complexity while maintaining a small generalization error.
In this paper, study the sample efficiency of canonicalization by comparing it with group averaging. We explicitly ask:
Which invariant function class (FGA or FCAN) requires a lower number of samples to generalize? Which one is more sample efficient?
We aim to provide meaningful answer to this question in the next section.
Assumptions. In this paper, we focus of finite subgroups G of the orthogonal group O acting on the input space 5d-1 := {z E Id || 1.. Note that our goal is to learn an appropriate base function f E such that, after applying the necessary transformations (either group averaging or canonicalization), we obtain a highly accurate estimator of f*. Therefore, we assume that learning base function f E J feasible. To formalize this, we avoid overly complex functions the base space by defining the set of base functions as polynomials of x E Sd with degree at most k E N:
F = =={(sE (3(5t))) f is polynomial of degree at most k
(5)
The parameter & E N controls the complexity of the base space (i.e., the number of parameters to learn). For small k, the focus on low-dimensional (i.e., smoother and simpler) functions, which generally easier to learn. Let the invariant function classes for the base space F be denoted as FAAN and F&A.
Target function complexity. We also need control the complexity of the target function f* (2((d-1), To achieve this, we adopt a common assumption from the literature, namely that f e H*(Sa-1), where H (Sdt-1 represents the Sobolev space with parameter 2 0. Formally, this space defined as:
H*(( =
f has square-integrable derivatives (on the sphere) up order }):
It is well known that to obtain continuous functions, one must assume > (d - 1)/2, which we adopt in this work. Additionally, larger values correspond the integrability of higher-order derivatives, leading to smoother functions.
On the restrictiveness of assumptions. In this paper, we restrict our focus to the sphere and finite matrix group actions for simplicity. While the setup can be extended to more general framework, we prioritize simplicity here. The choice of using low-degree polynomials for the base space closely related Sobolev kernels, which are commonly employed in machine learning and statistics. To obtain precise convergence rates for the generalization error (or excess population risk), we focus on low-degree functions, leveraging results from the theory of kernel convergence.
4
MAIN RESULTS
In this section, study generalization bounds for the problem of learning under invariances via canonicalization, as discussed in the previous section. We begin by studying and comparing the expressive powers of canonicalization and group averaging.
5

---

Published as a conference paper at ICLR 2025
4.1 WARM-UP: EXPLORING EXPRESSIVE POWER
Here, we compare the expressive power of FCAN and FGA, with particular interest in cases where the class of base functions we aim to use the next theorem to understand the expressive power for learnable functions, which constitute significantly smaller subset of the continuous functions class. Furthermore, the following result also provides better insights before we present the main generalization bound of the paper.
universally expressive (e.g., low-degree polynomials). Intuitively,
Theorem 1 (Expressive power of canonicalization). Consider an arbitrary vector spuce of base functions F, and assume it is closed under the group action, i.e, f'gx) E F for each f E F and g E G. Then, it follows that FCAN 2 FGA-
present the proof of Theorem Appendix
The above result indicates that if the set of learnable functions satisfies mild conditions (i.e., being vector space and closed under the group action), then canonicalization is always superior to group averaging in terms of approximation error. This implies that canonicalized models serve better approximators of the target function. However, from basic learning theory, we know that while larger function classes correspond to smaller bias, they also incur larger variance. Specifically, if FGA (or is close to lying within that space), then canonicalized models introduce more complexity into the learning task. In such cases, one might expect that
(6) Conversely, if the canonicalized model aligns with the target moactoon-meaninn that f E FCAN (or is close to lying within it), but f & FGA- one should expect that, for large sample sizes, the canonicalized model generalizes better due to lower approximation error:
Generalization Error of FGA < Generalization Error of FCAN-
Generalization Error of FCAN < Generalization Error of FGA-
This highlights a dichotomy regarding whether canonicalization outperforms group averaging terms of generalization and sample complexity. We will formalize this observation in the next subsection.
For the remainder of this subsection, we formally define the concept of alignment through a more concrete mathematical formulation in the context of approximation theory.
Definition (Alignment), A G-invariant target function f* E (2(ddtl) said to be f-aligned with the canonicalized models FEAN if and only if
min ||S - 1" S Ch-
fEJRAN
for all & E N, where C' is an absolute constant that does not depend k.
Observe that a larger value of 3 corresponds to greater alignment with canonicalized functions. Indeed, as B + co, the function becomes nearly aligned with canonicalized models even for finite k. For Sobolev target functions f* E HSd- alignment is only non-trivial when 3 > s.
Proposition 3. Any arbitrary G-invariant Sobolev function I* E H=((d=1) with parameter is s-aligned.
The proof of Proposition provided Appendix and is based on an equivalent definition of Sobolev spaces discussed in Appendix A. According to this result, in the remainder of the paper, will always consider cases where 3 2 s > (d - 2)/2.
To conclude this subsection, provide example to demonstrate that the inequality in Theorem I can be strict, meaning that there exist cases where FGA is a proper subset of FCAN, i.e., FCAN C FGA and FCAN + FGA-
Example Consider the space of linear functions defined as:
a, Vi E [d] a, E R
(9)
ieId
Let Pa denote the group of all permutation matrices (i.e., the symmetric group) acting on $d-1
Note that F_1 satisfies the condition stated in Theorem 1. We have
1 R[f((=) d!
Σ f(ax) Σ az dE
(10)
%E|d

---

Published as a conference paper at ICLR 2025
where Eieja at. In other words, Fax A is one-dimensional function class consisting solely of linear functioos of the form Eieja 24 for some a E R.
Now, let us consider canonicalized functions with respect to via the sort mapping: T(x) == "ini:x...,,max) In this case, if specifically consider functions restricted to /Pa then FOAN can represent any linear function Eie[g (cz;; the quotient space. In contrast, group averaging only able to represent functions of the form a Σieja 4;, even when restricted to quotient space. For a concrete example, consider the function f(x) = min 24. This function belongs to FCAN but is not in FG because it is not linear on S6-1, This demonstrates that JCAN D FGA and CANN # FGA- The same holds for Fk for all k E N. Remark 5. As vector spaces, note that dim(FCAN) = d while dim((Fa) 1. In other words, the gap between the two vector spaces can be arbitrarily large.
4.2 GENERALIZATION AND SAMPLE COMPLEXITY
In this section, we present the primary result of this paper, stated in the following theorem. Theorem (Generalization bounds for canonicalization). Consider the problem of learning under invariances with dataset S = {(r.. BR) i [nl] S (5tt-) x R)", consisting of n i..dd (labeled) samples, where = f (x;) + 6, and the independent noise terms e, are zero-mean with variance bounded by o² for all E [n]. Let JCAN and fGA denote the Empirical Risk Minimization (ERM) estimators derived from the invariant function classes FEAN and F respectively:
JCAN arg min SEFEAN
1 Σ ((f(z)),)).
(11)
Ti
iE(m)
FGA- = arg min JEFGA
(f((z))
(12)
n iE(n)
where ((())) denotes the squared loss. Additionally, assume the following conditions:
The optimal target function f belongs to the Sobolev space [1 with d-1
The function f is B-aligned with the canonicalization scheme for FCAN, where B 2 s.
Under these assumptions, we obtain the following bounds with high probability
|CCAN 1
$ $LCAN = Σ
dim((a
0² + k 22
(13)
LACS 1)
t=
Disgs ( LGA
σ²
dim dim(Y
k-
(14)
n
where Ya,t denotes the space of spherical harmonics of degree é over d variables (Appendix A), and YG C Ya denotes its projection onto the space of G-invariani polynomials.
The proof of Theorem 6 can be found in Appendix D, and comprchensive review of the theory of spherical harmonics is provided in Appendix A.
The generalization curves obtained for group averaging and canonicalization are illustrated in Figure 1. Let us interpret the upper bound in Theorem First, note that according to Appendix A, we have the following bounds:
21
k
21d -
dim(Ya.) (d 1)!
(1)),
Σ dim
(1 (1+ (1)),
(15)
Gl 1)!
where (1) as t oo. This leads to the following corollary.
In this paper, all high-probability arguments hold with least 90% probability.
7

---

Published as a conference paper at ICLR 2025
Corollary 7. Let us define the critical sample complexity Necitical as follows:
0² 22222-d-1
Neritical
(16)
(d- G "1 k2()-8))
Then, each of the following implications holds with high probability:
n S Neritical
= Lax S LCAN
(17)
n 2 Neritical
= LCAN S LGS.
(18)
Note that in the absence of alignment (i.e., 3 = s), we have that Neritical = oo and thus the latter case cannot occur, meaning that the upper bound obtained for canonicalization cannot outperform group averaging.
The proof of Corollary can be found in Appendix
To intuitively understand this phenomenon, note that when n S Naritical, we can disregard the second term in the upper bound and focus solely on the first term, which the dominating term. This first term quantifies the generalization eπrоr for the functions generated from FCAN or FGA without any bias. Since FGA represents a relatively smaller vector space (as established Theorem 1), conclude that group averaging is superior in these situations (i.e., it has lower variance).
Another way to interpret this regime is recognize that group averaging provides smoother approach to achieving invariant functions. In contrast, canonicalization involves composing base functions with the canonicalization (or projection) map т, which can discontinuous or non-smooth (see Section 2 for references).
On the other hand, when n 2 Neritical. the first term the upper bound becomes negligible, allowing us compare only the second term. If 3 > group averaging in terms of generalization error. Intuitively, this corresponds to cases where the canonicalization scheme is aligned with the optimal target function (i.e., B > s). This leads to the following conclusion:
conclude that canonicalization outperforms
Canonicalization outperforms group averaging when the sample size is sufficiently large. In such cases, the marginal gain canonicalization depends on the degree which the optimal target function is aligned with the canonicalization scheme.
is important to note that the alignment condition can be achieved either through an inductive bias or through learned canonicalization schemes. In both scenarios, our theory suggests that canonicalization superior, a conclusion that strongly supported by observations from previous tasks, such as those involving graph neural networks in machine learning.
Remark 8. The upper bound established in Theorem is tight in minimax sense, and we include proof of its optimality within the proof of Theorem 6. To attain this bound, one can utilize kernel regression within the space of (spherical) polynomials of degree at most This approach allows for achieving the upper bound by employing quadratic optimization to determine the optimal coefficients of the polynomial within the ERM objective. We provide a brief review of this in the proof of
Theorem as well.
Remark 9. It is important to note that the dependence of Neritical the group size |G| and the alignment parameter 3 is limited and negligible. other words, the threshold at which the phase transition occurs does not significantly depend the group size the level of alignment. However, improved alignment-strong scheme scheme--enhnnees the benefits of canonicalization in the large sample regime.
influenced by the parameter 3, the group, and the canonicalization
enhances
EXPERIMENTS
We present proof-of-concept experiments in this section. The primary focus of this paper to understand the generalization behavior of canonicalization and its comparison to group averaging. However, we aim to demonstrate that even in simple settings, alignment plays a crucial role in performance.
8

---

Published as a conference paper at ICLR 2025
Population Risk Alpha
3.0
Canonicalization Group Averaging
2.5
Population Risk
2.0
1.5
1.0
0.5
0.0
0.0
0.2
0.4
0.6
0.8 1.0
Alpha
Figure 3: Generalization behavior of canonicalization compared to group averaging.
5.1 ALIGNMENT
Consider a linear model built on top of polynomial features of degree at most 3 over
dimensional uniform data from the cube [|,, The training data consists of n = 100 independent and identically distributed samples uniformly drawn from [-1, 1]3, each labeled with the optimal
target function f and corrupted by Gaussian noise with standard deviation of = 1. We seek
permutation tnrrutttion-iivariantt estimator f. either via group averaging canonicalization, obtained through the least squares method.
The optimal target function, however, is assumed to be:
(*(x = a) (z + 2x² + 323) + a max(x1, 22, 23) 20 min(x1, x2, 23))
(19)
where 10 is hyperparameter. Note that - 0. f (x: becomes a linear but non- invariant function, making it difficult for both methods to learn. this scenario, group averaging performs better, as it at least interpolates smooth function rather than dealing with the non-smooth combination max / min. This case lacks alignment, and we expect group averaging to outperform canonicalization.
On the other hand, as a + 1, we have (x) = max(a1 22, 22, xz) - 20 min [21, 22, Tz). This function
better aligned with canonicalization rather than group averaging. The reason clear: is already expressed in terms of max min functions, which are easier for canonicalization to manage. In other words, the function is more aligned with canonicalization.
These intuitions are consistent with the results we present in Figure 3. In this figure, we run experiments based on the above setting with 100 training and test samples, and noise level a 1. The results clearly show how alignment influences the distinct performance between group averaging and canonicalization.
5.2 POINT CLOUDS
In this section, we conduct additional experiment to examine the theoretical results on the phase transition the sample complexity of canonicalization and group averaging.
We use the following setup: assume training set of n point clouds, each consisting of m points in d- dimensional Fuclidean space, modeled as elements of [-1,] mxx The point clouds are i.i.d. uniform samples from [-1, m|xdd The optimal target function assumed to be (x) max ||æz]|1. where
SE(R]
Iy denotes the L-th of the point cloud x E [-1, mxx (i.e., the points within the point cloud).

---

Published as a conference paper at ICLR 2025
This target function is invariant to permutations of the points in the point cloud. Let 0.1 denote the standard deviation of the Gaussian noise added to the training labels.
We train two-layer ReLU network with width of 20 on this dataset using mean-squared loss. Training is performed with SGD, using a learning rate of 0.01 for 100 epochs. Two methods are compared: group averaging (over all m!! permutations of the point clouds) and canonicalization (via lexicographic sorting of the point cloud rows). The test loss is calculated over 100 uniformly random point clouds sampled from [-1, m|add the test set.
For this experiment, we set m = = 5 and report the average test loss along with the standard deviation over runs for different numbers of samples n, shown below:
71 = 10
=
100
n 1000
Group Averaging
0.425:00.102
0.367
0.365 +0.094
00.054
Canonicalization
0.471 00.103
0.290
0.280=0.055
Table 1: Final test loss averaged over ten different random seeds.
The results reveal that when the number of samples n is relatively small, group averaging outperforms canonicalization, though the test loss remains relatively high for both methods. However, as the number of samples increases, canonicalization achieves better test loss. This behavior aligns with the theoretical findings of this paper and provides empirical support for them.
6 CONCLUSION
In this paper, we investigate generalization bounds for canonicalization as a method for constructing invariant function classes. As baseline, we compare it with group averaging. widely used approach for generating invariant functions. Our findings reveal two distinct regimes where canonicalization either outperforms or underperforms group averaging. in terms of the convergence of generalization error (i.e., sample complexity). Specifically, in the low-sample regime, group averaging proves superior due its smoother effect on the base function class. However, in the high-sample regime, canonicalization performs better, as it leverages the canonicalization (or projection) map achieve more accurate model approximations. This highlights the importance of aligning the canonicalization process with the target task, which we demonstrate to be crucial for building models with strong generalization capabilities. These results align with previous work in machine learning, particularly in areas like graph neural networks, where algorithmic alignment has been shown to enhance generalization.
ACKNOWLEDGMENT
This work was supported NSF AT Institute TILOS, ONR grant N00014-20-1-2023 (MURI MI.- SCOPE), and an Alexander von Humboldt fellowship.
REFERENCES
Francis Bach. Learning theory from first principles. MIT press, 2024. 19, 20
Simon Batzner, Albert Musaclian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Kornbluth, Nicola Molinari, Tess E Smidt, and Boris Kozinsky. Equivcaara graph neural networks for
data-efficient and accurate interatomic potentials. Nature communications, 13(1):2453, 2022. 1
Simon Batzner, Albert Musaelian, and Boris Kozinsky. Advancing molecular simulation with equivariant interatomic potentials. Nature Reviews Physics, 5(8):437-438, 2023.
Arash Behboodi, Gabriele Cesa, and Taco S Cohen. A pac-bayesian generalization bound for equivariant networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Gregory Benton, Mare Finzi, Pavel Izmailov, and Andrew G Wilson. Learning invariances in neural networks from training data. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 3
10

---

Published as a conference paper at ICLR 2025
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Marin Biloš and Stephan Günnemann. Scalable normalizing flows for permutation invariant densities. In Int. Conference on Muchine Learning (ICML), 2021. 3
Benjamin Bloem-Reddy, Yee Whye, et al. Probabilistic symmetries and invariant neural networks.
Journal of Machine Learning Research, 21990):1-61, 2020. 3
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017. 1,
Wee Chaimanowong and Ying Zhu. Permutation invariant functions: statistical tests, dimension reduction in metric entropy and estimation. arXiv preprint arXiv:2403.01671, 2024. 2024, 3
Nadav Dym and Steven J Gortler. Low-dimensional invariant embeddings for universal geometric learning. Foundations of Computational Mathematics, pp. 1-41, 2024.
Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel. Equivariant frames and the impossibility of continuous canonicalization. In Int. Conference Machine Learning (ICML), 2024. 3
Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. In Advances in
Neural Information Processing Systems (NeurIPS), 2021.
Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In Int. Conference on Machine Learning (ICML), 2021.
lan Goodfellow, Honglak Lee, Quoe Le, Andrew Saxe, and Andrew Ng. Measuring invariances in
deep networks. In Advances in Neural Information Processing Systems (NeurIPS), 2009. 3
Andrea Grisafi, David M Wilkins, Gábor Csányi, and Michele Ceriotti. Symmetry-adaptted machine learning for tensorial properties of atomistic systems. Physical review letters, 120(3):036002, 2018.
Geoffrey E Hinton. Learning translation invariant recognition in a massively parallel networks. In International conference on parallel architectures and languages Europe. pp. 1-13. Springer, 1987. 3
Oukour-umar Kaba, Amab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In Int. Conference on Machine Learning (ICML), 2023. 2,
Bobak Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, and Melanic Weber. On the hardness of
learning under symmetries. In Int. Conference Learning Representations (ICLR), 2024. 3
Jonas Köhler, Leon Klein, and Frank Noé. Equivariant flows: exact likelihood generative learning for symmetric densities. In Int. Conference on Machine Learning (ICML), 2020. 3
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
Zewen Li, Fan Liu, Wenjie Yang, Shoubeng Peng, and Jun Zhou. A survey of convolutional neural networks: analysis. applications, and prospects. IEEE transactions on neural networks and learning systems, 33(12):6999-7019 2021.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning, 2023. 3
Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expressive sign equivariant networks for spectral geometric learning. In Advances Neural Information Processing Systems (NeurIPS), 2024.
11

---

Published as a conference paper at ICLR 2025
George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonization perspective on invariant and equivariant learning. arXiv preprint 1XXv:22405.1837, 2024a.
George Ma, Yifei Wang, and Yisen Wang. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. Advances Neural Information Processing Systems (NeurIPS), 2024b. 3
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021. 3
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Int. Conference on Machine Learning (ICML), 2019. 1,3
Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score- based generative modeling. In Int. Conference on Machine Learning (ICML), 2020.
Siba Smarak Panigrahi and Arnab Kumar Mondal. Improved canonicalization for model agnostic equivariance. arXiv preprint arXiv:2405.1408, 2024.
Mircea Petrache and Shubhendu Trivedi. Approximation- geririniaannaaiiiitoon trade-offs under (approx- imate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 3
Omri Puny, Matan Atzmon, Heli Ben-Hamu, Ishan Misra, Aditya Grover, Edward J Smith, and Yaron Lipman. Frame averaging for invariant and equivariant network design. Int. Conference on Learning Representations (ICLR), 2022. 3,3
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas Guibas. Pointnet++: Deep hierarchical feature learning on point sets in metric space. In Advances Neural Information Processing Systems (NeurIPS), 2017b. 1
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter-sharing. In Int. Conference on Machine Learning (ICML), 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):11-80, 2008
Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2018. 3
Tess E Smidt. Euclidean symmetry and equivariance machine learning. Trends in Chemistry, 3(2): 82-85, 2021. 1.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of invariant classifiers. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2017. 3
Behrooz Tahmasebi and Stefanie Jegelka. The exact sample complexity gain from invariances for
kernel regression. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 3, 15
Choon Teo, Amir Globerson, Sam Roweis, and Alex Smola. Convex learning with invariances. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
Oliver Unke, Mihail Bogojeski, Michael Gastegger, Mario Geiger, Tess Smidt, and Klaus-Robert Müller. Se(3)-equivariaat prediction of molecular wavefunctions and electronic densities. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Martin Wainwright. High- dige-diien statistics: non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019. 20
12

---

Published as a conference paper at ICLR 2025
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Int. Conference on Learning Representations (ICLR), 2019a.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In Int. Conference Learning Representations (ICLR), 2019b.
13

---

Published as a conference paper at ICLR 2025
A BACKGROUND ON SPHERICAL HARMONICS
In this section, we review the theory of spherical harmonics, which provides a solid mathematical framework for understanding harmonic analysis on the sphere. This framework will be crucial for the proofs presented later the paper.
Let S {ir E R ||ح| 1} denote the unit sphere embedded in R For any continuous
function f E C(SA-1), we define its radial extension on IR \ {0} as follows:
f(z) = ||2||
This extension allows us to analyze the behavior of f not just on the sphere but also in the whole space Rd.
The spherical Laplacian, denoted by Aga-1, , is defined as:
A == AJ,
where A = Σ plays a pivotal role in spherical harmonic analysis.
i=1 oe represents the Fuclidean Laplacian operator acting in Rd. The operator A
A significant property of the spherical Laplacian A is that it is a self-adjoint operator on (S This self-adjointness ensures that the eigenvalues are real, and the eigenfunctions corre- sponding to these eigenvalues are orthogonal in the L sense.
To explore the spectral properties of As+ 1, we consider the vector space Va consisting of solutions to the following partial differential equation (PDE):
A Φ + 2Ø= = 0,
defined on the unit sphere. A remarkable result is that the dimension of this vector space is finite:
dim(VA) < 0o for all E
Moreover, the dimension of VA non-zero and only À takes the specific form:
X E(e d -
for some non-negative integer & This indicates that the eigenvalues of Aga-1 are discrete and non-negative, forming a countable set.
The corresponding cigenfunctions associated with these cigenvalues constitute orthonormal basis for the space LS( These eigenfunctions, known as spherical harmonics, are crucial in various applications, including solving partial differential equations, performing expansions in spherical coordinates, and analyzing functions on the sphere.
The space VA denotes the set of spherical harmonics corresponding the eigenvalue À = ((l d22). We let Φr. with E [dim(V [V)] represent an orthogonal basis of this space. In order to compute the dimension of Vx. refer to the established theory of spherical harmonics.
We know that the space Va can be expressed as:
VA [xx) / a homogeneous harmonic polynomial of degree with À = E(L d 2)}. 2
where a harmonic polynomial h R IR is defined polynomial that satisfies the condition
Ah = 0, with A being the Laplacian operator.
Let (RR)) denote the ring of homogeneous polynomials of degree l in variables. It can be shown that for any non-negative integer f, the relationship between the space of homogencous polynomials and the space of spherical harmonics can be expressed as:
Pr (()) Vicead 2) θ (P
(20)
where p2 - 2 22
2 is the radial polynomial. This decomposition reveals that the space of homogeneous polynomials can be broken down into the direct sum of spherical harmonics and a subspace generated by the radial component multiplied by lower-degree homogeneous polynomials.
Utilizing standard combinatorial arguments, we can derive the following corollary regarding the dimension of the space of spherical harmonics.
14

---

Published as a conference paper at ICLR 2025
Corollary 10. Let Ya, denote the vector space of spherical harmonics of degree f. Specifically, define Ya,e as Vi(e+d-2y Then, the dimension of this space can be computed as:
( ( dim(Ya,e) ( d ("+=-))
( d (10)))((+))) (t+d-3)
(21)
This result provides clear count of the dimensions of spherical harmonics in d-dimensional space, illustrating the rich structure of these functions. Moreover, it allows us to derive the dimension of spherical harmonics of degree at most & E N in the following lemma. Lemma 11.
We have the following asymptotic bounds for the dimension of spherical harmonics:
h
2k--11
dim((ae) = (d (d-1)! (1 (1))),
(22)
0
where 0% (1) - 0 as k- + co.
Proof. To establish this result, we begin by computing the sum of dimensions for spherical harmonics of degrees from 0 to k:
4: Σ
((+
((t-13) )
dim
(23)
t=
k: + (k+-T1)
k (
d- (
+
(24)
Thus, for large values of k,
k + d - 1)
d 1) + ( d-1
d 2)
dim(Ya,)) =
(25)
t=0
b
k
(1 + ok (1))
(d - 1)! (1+ (1))
(26)
(d 1)1
2k
(1 + on (1)).
(27)
(d - 1)!
This completes the proof.
Let us now compute the dimension of the vector space of spherical harmonics Y. that remain invariant under the action of subgroup G of the orthogonal matrices acting on 5d-1 According to the spectral theorems for invariant functions (Tahmasebi & Jegelka, 2023), we can derive the following result:
k
(1 (L+ (1))
&
2h dim))aa)) = G - 1)! (1 + ox)))
dY
Σ 2=0
(28)
G
Spherical harmonics also play a crucial role in our analysis of polynomial regressions throughout this paper. Specifically, the direct sum Di_ Ya,e corresponds precisely to the space of polynomials of degree at most & when we restrict our attention to the unit sphere.
We conclude this section by introducing the space of Sobolev functions (Sdd1) in the context of spherical harmonics. Let f (1d be a square-integrable function. From the properties associated with spherical harmonics, know that can be expressed as an infinite series:
dim(Ya.)
f(x)
Σ
feror (x),
(29)
t=
15

---

Published as a conference paper at ICLR 2025
where (Z), with L = 0, ..... and l' [Vi] form orthonormal basis for both spherical harmonics and L (Sdd-1) Indeed, these functions homogeneous polynomials of degree e as l varies.
Since f (S we can infer that
dim(Ya.)
Σ Σ
= 11==11flla 00.
(30)
The concept of Sobolev spaces involves placing restrictions on this space by imposing conditions on the rate at which the tail of the above series vanishes. For any non-negative s, we define
HS { (3 Ilf (8i-1)
(31)
dim(Ya.a)
Σ
e( < <oo (32)
One can prove that this new formulation is equivalent to the definition of Sobolev spaces presented in the main body of the paper.
B PROOF THEOREM
Proof. Let F be arbitrary vector space closed under the group action. We want to prove that FCAN 2 FGA. To this end, fix an arbitrary f E F and note that R[f] E FGA. Our goal is to show that R E FCAN and this completes the proof.
Note that for each E G, according to the closeness of F. under group action, we have f'gx) E F. Moreover, since F vector space, and thus being closed under taking summations, have that
Σ f(x)) F = R(f(() F.
(33)
GG|
DEG
Now let = (=][[[())) Then, according to the definition, we have that R(S(() E = R[)[((())) E FCAN.
(34)
However, R[f((x) FGA is G-invariant, thus have
R[f((x) = R())(=(x)).
(35)
for all v, which means that
R[((((())) FCAN R(f((a) FCAN,
(36)
and this completes the proof.
C PROOF OF PROPOSITION 3
Proof. Let f* H*(Sd-1) be a G-invariant function. To prove that f* is 3-aligned with the canonicalized models CAN with 3 = s, we need to show that
min |lf - 1- 112 1) CK
(37)
JEFL
for all & N, where C an absolute constant that does not depend k.
We begin by using Theorem 1, which implies that JLAN 2 F& for each k E N. The condition in Theorem holds here because F the space of harmonic polynomials degree at most k, is vector space that is closed under group action.
16

---

Published as a conference paper at ICLR 2025
Thus, have
min |lf fl 1) و
min Ilf
Mllzass 1);
(38)
FEFEAN
SEFGA
for each & N. Therefore, the proof is complete if we show that
min ||/ -V--fllae Mea(s--- Ck
(39)
JeF
for each & E N.
Let 1lg denote the orthogonal projection operator that projects square-integrable functions / (SS to homogeneous harmonic polynomials (i.e., spherical harmonies) of degree at most E N. We claim that [f*] E F&A and that
|| - f' I (
S c2
for constant C, which completes the proof.
First, since the Reynolds operator R commutes with I1, we have [[]][ = II, [R[["]] = [f"),
(40)
where we use R[ since f is G-invariant. This shows that [T([f*] E F&A by definition.
Next, we show that ||T[[[[]] - 1 12(s0-1) S 20 Let
dim(Ya.)
(())= Σ Σ
(e
8=1
where óe (z) (for = 0, l,... and l' E (Lim)(aa)))) form an orthonormal basis for both spherical harmonics and (gd--1)) Then we have
dim(Ya.e
|| MILASS--
Σ
P.e
1m1+1
8=1
Define μr = (e + d - 2) for each E N. We obtain
dim(Ya.))
[h [f*] - M (1
Σ
Σ
(Fie)2
(41)
k=++1
0
dim(Ya.)
Σ
Σ
Me peliee)
(42)
20 dim(Ya,))
S U4
pelSt,e)
(43)
(=
dim(Ya,e) Σ
= =k + 2 29
Helfie)
(44)
{=++1
8=1
Since μr increasing in E, follows that
dim(Ya,))
[f f l1 5 5k +d
(e(fi.))2
(45)
t=k+1
dim(Ya.d
< k 2s
20
pe(ft,e:)
(46)
1mk+1
00 dim(Ya.e)
< k 2s
Σ
melSie)
(47)
E=1
P=1
< k 20
| 11--(8--1y-
(48)
This completes the proof.
17
17

---

Published as a conference paper at ICLR 2025
D PROOF OF THEOREM 6
Proof. In this section, we present the proof of Theorem 6. First, we use a closed-form formula for the ERM estimator, then decompose the error into its bias and variance components. Finally, apply the analysis of random design linear regression to derive the result.
Consider a dataset S { MA : E [n]] S (5 x RR) consisting n i.i.d. labeled samples, where y4 = (x;) + t, and the independent noise terms E; are zero-mean with variance bounded by ²² for all i [n]. Let
FCAN = arg min Σ ((f(z)) JEPCAN
(49)
sE(n!
FGA arg min
Σ (((())))..
(50)
JEFOA
iE(m!
where ((:-)) denotes the squared loss. We aim to prove that for sufficiently large & E N, with high probability:
[CAN - - 12((8011) (
0²
dim( Yd,t)
k k29
(51)
E=0
|FGA - frr 1 12((8-11
Y 0²
dim
-2
(52)
n2
First, we focus on group averaging. We need introduce some notation, assuming the background provided in Appendix A. For any estimator, we have
dim(y
1xx) - Σ
where (x) denotes a basis for G-invariant spherical harmonics. We can rewrite the empirical risk minimization (ERM) loss function as follows:
k dim(
2
Σ v1) 1
1 - y/
(53)
For simplicity in notation. flatten our indices to = (f) E [p], where p = Ek dim (Y This avoids unnecessary dependence on previous notation for multiplicities.
d.e).
Next, we introduce the feature matrix = ( (z:)) nxp E BRP With a slight abuse of notation, we use / to denote both candidate estimator and its spherical coefficients. The ERM objective is:
Σ E(f(x;). v.) = Φ v112.
f = (ff) ER.
(54)
72
n
According to the closed-form solution of the above least-squares objective, obtain the following ERM estimator:
ブ=r-1o y. = + TT.
(55)
assuming invertible, which is equivalent to n 2 p in our case.
With slight abuse of notation, also f to denote the optimal target function and its optimal spherical coefficients. Replacing this into the population risk, we obtain:
F.AA - -f 12 1) =If f 2 211 1I 21
(56)
18

---

Published as a conference paper at ICLR 2025
where H1 denotes the orthogonal projection operator onto the space of spherical harmonics of degree at most k. We will treat the two terms on the right-hand side of the above inequality separately.
Let us first focus the first term. Let fx = I. and note that f f fex. Moreover, y = fx + 6 + e, where ó; == (z,) for any E [n].
To obtain upper bounds on the first term, utilize the derivation of f and write:
II - 11-13
Σ
+ 1 y-
(57)
Σ
1 0f +
8 E 1-
T c
(58)
(0)
(59)
<
2| o T
(60)
where (a) follows from the definition E.
We note that
E. I. c -'tr(0r--~-10))
(61)
= o T b
(62)
= =
(63)
where in the last step, we used the definition of 2. By straightforward application of the matrix Bernstein inequality (Bach, 2024, Proposition 3.12), we obtain that 1 - 1/4 with high probability if n 2 pp))(p). Using Markov's 's inequality, this leads us to
o²p
Tel
with probability least 99%.
(64)
n
Next, we derive upper bounds
| 14 8 2
Note that
T 81[21 E[tr(6 1o 1 8)1 Ex
(65)
E[tr(60 +Σ 1--
(66)
E[[|88"
|| 1 [|
(67)
[[]|88 || -up=-~'"" ' }]
(68)
where | Ir denotes the Frobenius norm. Note that ||65T || = ||01| Moreover, tr(0E-15-10)
tr(E-
Thus, we have
E. + 5| <
|||0||| tr(E-
(69)
Similar to the previous case, we know that with high probability, nI = 1/ 2 x Also.
B 1 = EE [xx(1)) = 11/2x112
(70)
This allows us to conclude that:
81 - T
1
with probability at least 99%.
(71)
We are now ready to combine all the above high-probability arguments to get:
o²p n
|IACA f -
+ llfe with probability at least 99%.
(72)
Now let us compute |f 12. Similar to the proof of Proposition 3, we obtain
1ff < 28 11 1
(73)
Therefore, we have
0²p h 22
| f* I ( S
with probability at least 90%,
(74)
which completes the proof.
19

---

Published as a conference paper at ICLR 2025
The proof for FAN is also similar, avoid repeating the arguments. The only difference is that we explore all harmonic polynomials of degree at most k, instead of G-invariants, which corresoonds to having larger first term above. But, the second, term corresponding to the approximation error improved, as we use the alignment hypothesis instead of the Sobolev condition.
Remark 12.
Remark 13. All these bounds are optimal in minimax sense according to standard bounds in the literature (Bach, 2024; Wainwright, 2019). As the main focus of this paper is not on serving optimal bounds and solely on understanding achievable rates for canonicalization, we avoid rewriting optimality proofs here to keep the paper concise.
E PROOF OF COROLLARY 7
Proof. To derive formula for the critical sample complexity Neritical, note that have already shown the following using Lemma 11 to hold with high probability:
[CAN - 5z) 1-1 12((801)
S
2h
2h
0²
+ k
28
(75)
(d 1)!
| - 1-1 112(84-1)
2h 21-
o² k k2
x (d 1)! G//n
(76)
Therefore, to obtain the phase transition, we solve
2k o²
2h
0²
+ k k22
(77)
1)! N Neritical
(d 1)! |G |e|Neritical
This leads to
22
Neritical
(78)
(d 1-)) G (1 - 2:2 2:2
The proof is thus complete.
L
20


Reviews:
[{"review_id": "9BRA1Ll9Zu", "reviewer": "Reviewer_JVqd", "summary": "This paper addresses this gap by theoretically examining the generalization benefits and sample complexity of canonicalization, comparing them with group averaging, another popular technique for creating invariant or equivariant function classes.", "questions": "none", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It provides new insights into the generalization bounds of canonicalization and enriches related theoretical research. By comparing with the group averaging method, it highlights the advantages and disadvantages of different methods and provides practical references for researchers. The paper has a reasonable structure, clear logic, and is easy for readers to understand. The paper studies topics of great significance in machine learning and statistics, which is in line with current research trends.", "weaknesses": "Although the theoretical analysis is thorough enough, it might be helpful to add some experiments to ensure empirical support.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WY4M4Nx22U", "reviewer": "Reviewer_cZFY", "summary": "The paper theoretically investigates the generalization error of canonicalization vs group averaging. The theoretical results suggest that the generalization performance of canonicalization and group average depends on the trade-off between variance and bias (approximation error), where group averaging being superior in variance (by a factor of group size) and canonicalization being superior in bias based on a newly defined alignment metric. The authors also provide a set of proof-of-concept simulation to show that group averaging and canonicalization outperforms each other under different true functions.", "questions": "1. The authors mentioned in the literature review that people have studied the generalization error of group averaging for kernel methods. However, how does existing bound compares with the bound derived by the authors is not discussed. Can the author share some details on this matter and remark the novelty here?\n\n2. I have a minor question regarding the example 4 and please correct me if I am wrong. The example is given to demonstrate when the closed space assumption is violated, there could be cases where $F_{GA}$ is not a subset of $F_{CAN}$. However, as stated in line 300, \"the function belongs to $F_{CAN}$ but not $F_{GA}$, which suggests $F_{GA}$ is not a subset of $F_{CAN}$.\" I am not quite following the logic here as I believe we need something on the contrary right?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Theoretical results have consistent notations and are easy to follow.\n\n2. The theoretical results shows the interesting trade-off between bias and variance in the generalization error of canonicalization and group averaging, where canonicalization, in general, has better bias and worse variance. This alludes to the idea that canonicalization might benefit in the case of large data size.\n\n3. The trade-off also results in a critical data size value, which unveils an indicator to compare group averaging and canonicalization.", "weaknesses": "1. Corollary 7 seems to be useful and interesting at the first glance, but there are some issues with it. First of all, equation (17) and (18) could be stated more carefully even though the idea is intuitive, as the main theorem provides upper bound rather than precise value (which could make the argument false with small probability). Second, the critical value depends on some factors that are practically intractable, mainly the $\\beta$ alignment factor, but also the noise level. Third, in the case of $\\beta = s$ as suggested in Proposition 3, the critical value goes to infinity, which suggests canonicalization will always be inferior.\n\n2. The statement of Proposition 3 might also cause confusion. First, it is better to state the function class here to remind the reference function class when talking about alignment. Second, upon further reading into the Appendix C, it seems the statement should be $\\beta \\geq s$ rather than $\\beta = s$ (The authors discussed this relation above and below the paragraph, but it could be better to have it in the statement unless there are concerns the authors like to clarify), as this $s$ derivation is based on group averaging and Theorem 1. Also, when $s=\\beta$, it actually causes problem in Corollary 7, where the critical value will go to infinity, which suggests canonicalization will always be worse for G-invariant Sobolov function with parameter s.\n\n3. Simulation is lacking. The provided simulation does align with the general intuition that when the true function is close to the canonicalization representation, canonicalization could do better. However, this simulation does not provide any insights on the effect of data size, which is the main theoretical contribution of the work (the error comparison over the number of observations). I hope the author could at least provide a simple set of simulations that shows the error decay of group averaging vs canonicalization which shows the two converge as n increase and then canonicalization takes the lead. I also suggest investigating the empirical critical value (when error of group averaging starts to surpass canonicalization) over different factors to see whether Corollary 7 could have practical implications for future iterations (considering the limited time for the rebuttal).\n\n1. There are some minor typos that might confuse some readers. For example, one super-script G is missing in equation (15).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BS0nUWw0dk", "reviewer": "Reviewer_ekUV", "summary": "This is a theory-oriented paper focusing on the generalization bounds of canonicalization. Specifically, it introduces the concept of \"alignment\" to describe the performance differences between canonicalization and group averaging under various conditions. Following the theoretical analysis, a proof-of-concept experiment is presented to support the conclusions.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The organization and writing of this paper are reader-friendly.\n2. The good generalization analysis aids researchers in understanding, designing, and applying canonicalization and group averaging techniques.\n3. According to the authors, this is the first theoretical exploration of performance differences between canonicalization and group averaging under varying conditions.", "weaknesses": "1. The experiment section would benefit from more case studies.\n2. There is no specific description of sample generation in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uwgql7j9UC", "reviewer": "Reviewer_1T9x", "summary": "Existing studies have explored the expressive power and continuity of functions represented through canonicalization, but its generalization ability remains underexamined. This paper fills this gap by providing a theoretical analysis of the generalization benefits and sample complexity associated with canonicalization, comparing these attributes with group averaging—a widely used technique for constructing invariant or equivariant function classes.", "questions": "See \"Weaknesses\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper fills the gap in theoretical analysis within the field of XX.\n2. The paper provides detailed proofs for all theoretical results.\n3. The paper demonstrates the validity of the proposed theoretical results through experiments.", "weaknesses": "1. The details of the proofs need to be refined, as the reasoning in many steps is not particularly straightforward.\n2. As a paper focused on statistical theory, it would be best to outline the structure of the proofs to facilitate understanding.\n3. Some definitions seem to be incorrect. For example, on the left of Eq. (2), the function $R(f)$ has no independent variable $x$, but $x$ appears on the right of Eq. (2). The similar problem also exists in several place of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)