Learning with Exact Invariances in Polynomial Time

We appreciate the reviewer’s recognition of our work’s merits and their valuable comments.

The claim that the proposed algorithm produce a predictor that achieves exact invariance in time logarithmic in the size of the symmetry group is supported by two results: a nice property of groups (provided on page 5) and fact that the size of the group generator is bounded by the logarithm of the group size (Appendix C1). Is the returned predictor f' (truncated to at most D eigenvectors) is a "good" approximation of the optimal Sobolev regressor f* ? There are no equations that show precisely how close f' is to f*. The third equation on page 6 does provide important information on this missing link but it does not provide all the information. It seems to me that the learning objective should be instead to find an invariant f' that should be as close as possible to the best invariant regressor f**. This f** is the one satisfying the optimization problem given by the last equation on page 6. Consequently, it would be nice if the authors could establish an upper bound on E_S || f' - f** ||^2_L2 as a function of s,d, and n. I think this is actually what is missing in this paper. However, I think that the contributions of this paper are already substantial enough to be presented at ICML.

Answer: Thanks for your interesting question! In our problem setting, the function $f^\star$ is invariant, which implies that $f^{**} = f^\star$ (using the reviewer's notation—i.e., the 'best' invariant estimator is the optimal regressor $f^\star$). The distance between $\hat{f}$ and $f^\star$ is measured using the formula $\mathcal{R}(\hat{f}) = \mathbb{E}_S[ \lVert \hat{f} - f^\star \rVert^2]$, and this quantity is explicitly upper bounded as a function of $n$, $s$, and $d$ in Theorem 1 (second item, line 207).

This is a theoretical paper and the presented theory is nice an relevant; but ... I think the authors should provide the motivation for considering Riemannian minifolds.

Answer: Thank you for your question and constructive suggestion. We considered boundaryless Riemannian manifolds in order to present a general theory that holds in a wide range of settings. Note that the boundaryless assumption is primarily for simplicity, to avoid technical complications related to boundary behavior when defining eigenfunctions. The theory can be extended to manifolds with boundaries under standard regularity assumptions on the boundary. However, we agree that compact subsets of Euclidean spaces are more familiar and accessible to the ICML community. We will revise the paper accordingly in the next version to reflect this suggestion.

You should provide a citation for the result of the expected population risk (in fact, the expected excess risk) of the KRR estimator on page 3.

Answer: Sure, thanks for your suggestion! The bound is derived in several standard references, such as [1], and we will add the appropriate citations to the paper.

The book of Sholkopf ans Smola was published by MIT Press in 2002, not 2018.

Answer: Thanks for pointing this out! We will correct it in our next version!

There are a few conflicting notations. In the supplementary material, g is used to represent a group element and the metric tensor!

Answer: Thanks for pointing this out! Since we frequently use $g$ to denote group elements, we will revise the notation for metric tensors to avoid any confusion.

\eta is the regularizer of the KRR of Equation 8. But that regularizer is referred to as \lambda on page 8.

Answer: Thanks for pointing this out! Yes, in this case, using the notation $\lambda$ instead of $\eta$ is confusing, as $\lambda$ can also be considered as an eigenvalue and so be related to $D$, as discussed in Section 6.1. We will correct this to avoid any confusion.

What happens if G does not form a group? For example if you translate an image, it will eventually fall off the boundary and the inverse translation does not exists. This happens often. How can you address this problem?

Answer: Thanks for raising this interesting question. If $G$ is not a group, it is still possible—under certain conditions—to obtain a sequence of linearly constrained quadratic programs for this problem. The main challenge in such cases is that the existence of a logarithmic-sized generating set is not guaranteed. To address this, one could consider alternative algebraic or analytic approaches to construct suitable "generating sets" for these settings. In our opinion, it may be possible to extend the results to such cases by imposing appropriate assumptions. We will include a discussion of this in the final version of the paper.

[1] Bach, Francis. Learning theory from first principles. MIT press, 2024

We appreciate the reviewer for acknowledging the merits of our work and for raising interesting questions.

The algorithm relies on oracle access to the geometric properties of the input space, which may not always be available in practical applications.

Answer: Thanks for mentioning this interesting feedback. Yes, in general, computing even the first non-zero eigenvalue of the Laplacian can be a very challenging problem in the geometry of manifolds. However, in practical scenarios, we often deal with group actions encoded via matrices over algebraic spaces (such as polynomials), which allows us to access the oracle through polynomial evaluations or by computing products of polynomials (see lines 180–190, second column). Such settings include tori, Stiefel manifolds, spheres, and direct products of these spaces. We present the result for arbitrary manifolds to keep the paper’s contributions broadly applicable, and to highlight that the difficulty of the problem on arbitrary manifolds arises from intrinsic geometric properties, rather than from the learning task itself. We discuss this further in the next version of the paper. Thus, the result applies to practical settings, and the oracle assumption is not restrictive in the problems we often encounter in practice.

In Algorithm 1, we don't know alpha in practice. How does this affect the efficiency of the proposed algorithm?

Answer: Thanks for pointing this out. According to our proof, we only require a lower bound on $\alpha$ to run the algorithm, and the proof remains valid under such settings. Therefore, it is sufficient to know that the optimal function satisfies at least some degree of smoothness, as encoded by $\alpha$. We will incorporate this clarification into the next version of the paper.

Thanks a lot for your valuable feedback and constructive comments regarding additional experiments. While we mention that we are committed to including additional detailed experiments in the camera-ready version of the paper, we would like to emphasize that the main focus of this work is theoretical, and it lies within the domains of statistical learning theory and computational problems in statistics. We hope the reviewer will kindly reconsider their evaluation in light of this context.

the paper should empirically compare .... the invariance error of the trained model to ordinary kernels even if the results seem obvious.

The invariance error (referred to as Invariance Discrepancy in Section 6.3 of the manuscript) of the trained model using our method (Spec-AVG) is zero; this is why we did not include invariance error of Spec-AVG in the plots. We will add a note in the caption of Figure 1 to make this clearer in the camera-ready version of the manuscript.

Plots of experiments showing the invariance error of ordinary Kernel Ridge Regression (KRR) are provided in Figure 1 of the appendix, serving as proof of concept that KRR is not inherently invariant. This experiment highlights the need for additional considerations beyond the KRR estimator to achieve exact invariant estimators, even in practice.

... empirically compare actual running times even if the results seem obvious ... at least one real dataset, such as from the UCI repository ...

Thanks a lot for your thoughtful suggestion. We will include additional experiments on the prohibitively high running time of existing algorithms for real datasets to further support our motivation in the camera-ready version of the manuscript. As you clearly noticed, the computational costs of existing algorithms that require enumeration over all group elements—such as group averaging and data augmentation—are extremely high. For example, in the case of permutations, the complexity is at least of order $\Omega(d!)$, which becomes infeasible even for relatively small values of $d$—e.g., when $d = 20$, the number of permutations is already $20! \approx 2.43 \times 10^{18}$, which is about 2 million times larger than the estimated 1.2 trillion parameters of GPT-4 [1] :D.

... If a large number of bases is necessary in real cases, this method might not be beneficial ...

Thanks a lot for your interesting question. Similar estimators that use a cutoff for the number of bases are very classical in statistics, especially in density estimation. Indeed, in many density estimation problems, this class of estimators is known to be minimax optimal and is often the only efficient choice.

It is important to note that the number of bases, $D$, required by our algorithm (Spec-AVG) is $n^{1/(1 + \alpha)}$, where $\alpha \in (1, \infty)$. Please refer to Line 1 of Algorithm 1. Thus, $D$ is at most $\sqrt{n}$, which is relatively low and practical.

In Figure 2 of the appendix, we provide plots of Spec-AVG with different choices of $D$, as well as KRR with varying regularization parameters $\eta$, to illustrate the effect of hyperparameters on population risk. We are committed to providing further experiments—including those on real-world datasets—for the camera-ready version of the manuscript to fully address your concern.

... approximating group averaging by randomly sampling group elements ...

The focus of this work is on the theoretical computational-statistical trade-offs in learning with exact invariances, and random sampling does not guarantee exact invariance; hence, it falls outside the scope of this work.

The notations $D^\lambda$ and $D_{\lambda}$ are pretty confusing.

Thank you for pointing this out! We agree with the reviewer that the notation is confusing, and we will revise it in the final version of the paper.

[1] https://medium.com/%40ceo_44783/why-i-prefer-gpt-4-over-gpt-4o-cf504741e156

Thank you very much for your positive and constructive feedback. We’ve done our best to address your concerns in detail below, and we hope this will support a more favorable evaluation and score of our work.

Conducting more numerical experiments could help demonstrate the proposed algorithm's improvements in computational efficiency and its ability to enforce group invariances while maintaining the same learning rate as the original KRR. Additionally, it would be beneficial to compare the proposed algorithm with other state-of-the-art methods, such as GNNs. However, as a theoretical paper, this should be acceptable in this regard.

Answer: Thanks for your suggestion! While we are committed to adding additional detailed experiments in the camera-ready version of the manuscript, as noted by the reviewer, the main focus of this work is on the computational complexity of learning and is primarily theoretical in nature.

Could the analysis of the main theorem be extended to cases where the regression function does not belong to the hypothesis space? Could Algorithm 1 be combined with other large-scale optimization methods, such as kernel conjugate gradient methods with random projections or divide-and-conquer kernel ridge regression?

Answer: Thanks for your interesting and thoughtful question. The analysis could be extended to cases where the regression function is not in the hypothesis space, under certain conditions. For instance, if the regression function does not belong to the Sobolev space of order $\alpha$ (the space in which we perform KRR), but instead belongs to another Sobolev space of order $\beta$, then it is possible to extend the theory and obtain generalization bounds. However, for arbitrary functions, it is not clear how to identify an appropriate RKHS that would allow the proof to be adapted to such settings. In our opinion, addressing this challenge may require problem-specific approaches.

Regarding computational efficiency, large-scale KRR methods are indeed useful for alleviating the computational complexity of kernel methods, which typically involve matrix inversions and require $O(n^3)$ time. These methods effectively reduce one polynomial-time algorithm to another with lower polynomial-time complexity. In contrast, our goal is to propose a polynomial-time solution for a problem whose current solutions have (super)exponential time complexity. In our current setting, it is not clear how to further reduce the complexity using large-scale KRR techniques, and we defer adapting the algorithm to such settings to future work.

Thanks a lot for your positive and constructive feedbacks.

The paper only provides a simple experimental evaluation, which, as stated above, focuses on a single comparison with KRR. A possible interesting addition would be to provide comparisons with other invariant methods such as group averaging, frame averaging, and data augmentations. While this addition is not necessary since the focus of this work is more theoretical, it will better showcase the disadvantages of the alternative methods in an experimental setting.

Answer: Thanks for your suggestion! While we are committed to adding additional detailed experiments in the camera-ready version of the manuscript, as noted by the reviewer, the main focus of this work is on the computational complexity of learning and is primarily theoretical in nature.

One possible limitation of the proposed method is the focus on discrete symmetry groups. This is not exactly a weakness, but it can limit the setting in which the proposed algorithm can be utilized.

Answer: Thanks for pointing this out! Extending the results to infinite groups is an interesting and relatively challenging direction for future work of this study. We appreciate the suggestion!