Generalization Bounds for Canonicalization: A Comparative Study with Group Averaging

We thank the reviewer for their positive feedback on our paper, and we apologize for the delay in responding due to personal circumstances.

---

Response to Weakness 1 & 2

Thank you for raising this issue! We have made small changes to the appendices in the revised version to improve the readability of the proof. Additionally, following the reviewer’s suggestion, we have added a new paragraph at the beginning of the proof of the main result (Appendix D, hihglighted in blue), providing an outline of the proof.

---

Response to Weakness 3

Thank you for pointing this out. We reviewed the paper and made minor changes to improve the notation and correct typos. Regarding the specific point mentioned by the reviewer, we agree that the previous notation was confusing and have updated it as follows: For any function $f$, we now use $\mathcal{R}[f]$ to denote the result of applying the Reynolds operator to $f$ (i.e., group averaging). Since $\mathcal{R}[f]$ is also a function, it can be evaluated as $\mathcal{R}[f] (x)$, which means the function $\mathcal{R}[f]$ evaluated at $x$. This notation has been updated throughout the paper, including in Equation (2), which was specifically mentioned by the reviewer (highlighted in blue).

---

We are also pleased to report that, following suggestions from other reviewers, we conducted a new experiment during the rebuttal period. This experiment empirically validated the phase transition proved in the paper regarding the sample complexity of canonicalization. These findings have been added to Section 5.2 of the revised paper (highlighted in blue).

---

We would greatly appreciate your feedback on the updated version and would like to know if your concerns have been adequately addressed. Thank you!

We thank the reviewer for their positive feedback on our paper, and we apologize for the delay in responding due to personal circumstances.

---

Response to Weakness 1

Thanks for raising this issue! To follow the suggestion, we conducted a new experiment to empirically validate our theoretical comparison between canonicalization and group averaging. While our previous experiment focused on the concept of alignment, the new experiment examines the role of sample size in determining the superiority of group averaging versus canonicalization. Specifically, we used point clouds invariant under permutations of their points and compared group averaging with canonicalization (via lexicographic sorting) to derive invariant function classes. Given the computational complexity of averaging over the entire permutation group, we restricted the experiment to point clouds with five points.

Our findings demonstrate that group averaging is superior when the sample size is small, whereas canonicalization outperforms it as the sample size increases. These results align with the theoretical predictions in our paper.

The new findings have been added to the revised version of the paper (Section 5.2, highlighted in blue).

---

Response to Weakness 2

Thank you for pointing this out! We have revised the paper (Section 5.1) to include additional details about the sample generation process (highlighted in blue). Specifically, we used $n$ i.i.d. samples from $[-1, 1]^d$ for both the training and test datasets, with $n = 100$ and $d = 3$.

---

We would greatly appreciate your feedback on the updated version and would like to know if your concerns have been adequately addressed. Thank you!

Response to Question 1

Thank you for asking this question. We note that the study of sample complexity for group averaging in kernel methods heavily relies on the concept of sparsity. Kernels, under mild conditions, adopt spectral representations (via, e.g., Mercer's theorem) and often lead to an infinite-dimensional spectral feature vector that becomes sparse when we apply group averaging over the kernel to restrict to invariant functions. Therefore, the key distinction when comparing group averaging with non-invariant kernel methods is whether sparsity is present.

However, in our paper, we focus on comparing canonicalization with group averaging, where the concept of sparsity is no longer sufficient. While we used sparsity to derive the bound for group averaging, for canonicalization, we introduced the notion of alignment, which is fundamentally independent of the sparsity-based approach used in previous works.

[1] Bietti, Alberto, Luca Venturi, and Joan Bruna. "On the sample complexity of learning under geometric stability." Advances in neural information processing systems 34 (2021): 18673-18684.]

[2] Tahmasebi, Behrooz, and Stefanie Jegelka. "The exact sample complexity gain from invariances for kernel regression." Advances in Neural Information Processing Systems 36 (2023).

[3] Elesedy, Bryn. "Provably strict generalisation benefit for invariance in kernel methods." Advances in Neural Information Processing Systems 34 (2021): 17273-17283.

[4] Mei, Song, Theodor Misiakiewicz, and Andrea Montanari. "Learning with invariances in random features and kernel models." Conference on Learning Theory. PMLR, 2021.

---

Response to Question 2

Thanks for pointing out this issue! The purpose of Example 4 is to complete what we proved in Theorem 1 about $F_{CAN} \supseteq F_{GA}$.

In that example, we show that there are cases, that satify the condition in Theorem 1, and we have $F_{CAN} \supset F_{GA}$ and $F_{CAN} \neq F_{GA}$. In other words, the example show that there are cases that $F_{GA}$ is a proper subset of $F_{CAN}$. We made changed to clarify this in the revised version (paragraph before Example 4, highlighted in blue).

---

We would greatly appreciate your feedback on the updated version and would like to know if your concerns have been adequately addressed. Thank you!

We thank the reviewer for their positive feedback on our paper and their recommendation to include additional experiments. We apologize for the delay in responding due to personal circumstances.

---

Response to Weakness 1

Thanks for your comment! First, we agree with the reviewer that Equation 17 and Equation 18 can be stated more formally. Therefore, in the revised version, we followed the reviewer's suggestion and made Corollary 7 more formal (highlighted in blue).

Second, we aggree that the critical value depends on the problem's parameters which can be difficult to estimate in practice. In the paper, our foucs was to show that the phase transition exists, and to show that the critical value depends on the problem's parameters via the given formula, assuming that we have some knowledge of the taks and the model.

Third, the reviewer’s point about there being no gain in canonicalization when $\beta = s$ is exactly correct, as it corresponds to the case where no transition occurs. Intuitively, this situation arises when the canonicalization map introduces unnecessary complications (e.g., non-differentiability) into the problem. As a more concrete example, if the optimal target function is a permutation-invariant linear function on $\mathbb{R}^d$, then performing group averaging over the space of linear functions is indeed superior to canonicalization (e.g., via sorting the vector), since the canonicalized function class is larger (Theorem 1), thereby introducing more variance, while the bias of both group averaging and canonicalization is zero in this case. We have also added a clarifying sentence about this phenomenon in Corollary 7.

---

Response to Weakness 2

Thank you for pointing out the ambiguities in the statement of Proposition 3. We would like to clarify that the proposition holds only when $\beta = s$, and not for larger values of $\beta$. To understand this, we note that the definition of Sobolev space involves a specific decay of the spectrum (Equation 31 in the paper), which allows us to conclude the result only for $\beta = s$.

Furthermore, we agree with the reviewer that if $\beta = s$, there is no gain in canonicalization, as in this case no alignment occurs in the problem to any extent.

The statement of Proposition 3 has been revised in the paper to address the reviewer’s concerns (highlighted in blue).

---

Response to Weakness 3

Thanks for your recommendation to include additional experiments! To follow the suggestion, we conducted a new experiment to empirically validate our theoretical comparison between canonicalization and group averaging. While our previous experiment focused on the concept of alignment, the new experiment examines the role of sample size in determining the superiority of group averaging versus canonicalization. Specifically, we used point clouds invariant under permutations of their points and compared group averaging with canonicalization (via lexicographic sorting) to derive invariant function classes. Given the computational complexity of averaging over the entire permutation group, we restricted the experiment to point clouds with five points.

Our findings demonstrate that group averaging is superior when the sample size is small, whereas canonicalization outperforms it as the sample size increases. These results align with the theoretical predictions in our paper.

The new findings have been added to the revised version of the paper (Section 5.2, highlighted in blue). We also plan to study the dependence of the critical sample complexity on the problem's parameters through experiments, and we will include these results in the next version of the paper (due to time constraints during the rebuttal period).

---

Response to Weakness 4

Thank you for pointing out the typo! We made a pass through the paper and corrected all typos we found, including the one you mentioned, in the revised version.

We thank the reviewer for their positive feedback on our paper and their recommendation to include additional experiments. We apologize for the delay in responding due to personal circumstances.

To follow the suggestion, we conducted a new experiment to empirically validate our theoretical comparison between canonicalization and group averaging. While our previous experiment focused on the concept of alignment, the new experiment examines the role of sample size in determining the superiority of group averaging versus canonicalization. Specifically, we used point clouds invariant under permutations of their points and compared group averaging with canonicalization (via lexicographic sorting) to derive invariant function classes. Given the computational complexity of averaging over the entire permutation group, we restricted the experiment to point clouds with five points.

Our findings demonstrate that group averaging is superior when the sample size is small, whereas canonicalization outperforms it as the sample size increases. These results align with the theoretical predictions in our paper.

The new findings have been added to the revised version of the paper (Section 5.2, highlighted in blue).

We would be happy to hear your feedback on the updated version and to know if your concerns about the experiments have been adequately addressed. Thanks!