Learning with Exact Invariances in Polynomial Time
Authors: Ashkan Soleymani
Behrooz Tahmasebi
Stefanie Jegelka
Patrick Jaillet
Venue: ICML 2025 spotlightposter (2025)
Keywords: Learning with Invariances
Kernels
Spectral Theory
Primary area: general_machine_learning->kernel_methods
TL;DR: We propose a polynomial-time algorithm for learning exact invariances through kernel regression on manifold input spaces.

Abstract: We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with *exact* invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem.  To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (as opposed to approximate) invariances in this setting. In developing our approach, we also resolve a question recently posed by Dıaz et al. (2025) on efficient computation of invariant bases and kernels with respect to finite groups, even when the group size is prohibitively large. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.

Learning with Exact Invariances in Polynomial Time
Ashkan Soleymani" Behrooz Tahmasebi 2
Stefanie Jegelka Patrick Jaillet'
Abstract
under the symmetries inherent in the data. This framework is broadly applicable across various domains in the natural sciences and physics, including atomistic systems (Grisafi et al., 2018), 1), molecular wavefunctions and electronic den- sities (Unke et al., 2021), interatomic potentials (Batzner et al., 2022), and beyond (Batzner et al., 2023). While many applications involve Euclidean symmetries (Smidt, 2021), the scope of such methods extends well beyond them to other geometries (Bronstein et al., 2017).
We study the statistical-cone ciniutacallcmpputttioonlall trade-offss for learning with exact invariances (or symme- tries) using kernel regression. Traditional meth- ods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide polynomial-time solution are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-ting gorithm that learns a classifier with exact invari- ances. Moreover, our approach achieves the same excess population risk (or generalization error) the original kernel regression problem. To the best of our knowledge, this is the first polynomial- time algorithm to achieve exact (as opposed to approximate) invariances in this setting. In devel- oping our approach, we also resolve a question recently posed by Díaz et al. (2025) on efficient computation of invariant bases and kernels with respect to finite groups, is prohibitively large. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation the problem of Iearn- ing under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.
al-
Learning with invariances has longstanding history in ma- chine learning (Hinton, 1987: Kondor, 2008). In recent years, there has been significant interest the development and analysis learning methods that account for various types of invariances. This surge interest is strongly mo- tivated by many models showing considerable success in practice. Empirical evidence suggests the existence of algo- rithms that can effectively learn under invariances while ex- hibiting strong generalization and computational efficiency. However, from a theoretical perspective, much of the fo- cus has been on the expressive power of models, gener- alization bounds, and sample complexity. There remains relative lack of understanding regarding the statistical- computational trade-offs in learning under invariances, in foundational settings such as kernel regression.
when the group size
Symmetries can be incorporated into learning in multiple ways. An immediate solution for learning with invariances seems to be data augmentation over the elements of the group. Moreover, some approaches learning with invari- ances rely on group averaging, a technique that involves summing over group elements. However, the typically large size of the group can make both of these approaches com- putationally prohibitive, even expreeexponettill in the di- mension of input data. Alternative approaches, such as canonicalization and frame averaging, also suffer from is- sues like discontinuities and scalability challenges (Dym et al., 2024).
1. Introduction
While humans can readily observe symmetries invari- ances in systems, it is generally challenging for machines to detect and exploit these properties from data. The ob- jective of machine learning with invariances is to develop approaches that enable models to be trained and utilized
'Equal contribution 'MIT EECS and MIT LIDS "MIT EECS and MIT CSAIL "School of CIT. MCML, and MDSI, Technical University of Munich (TUM). Correspondence to: Ashkan Soleymani <ashkanso mackaanso@mitedu...... Behrooz Tahmasebi <bzt@mit.cdu>.
This paper seeks to address the following question:
Can we obtain an invariant estimator for learning with invariances that achieves both strong general- ization and computational efficiency?
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The first contribution of this work is a detailed study of

---

Learning with Exact Invariances in Polynomial Time
the problem of learning with invariances in the context of kernel methods. Kernels, which have been among popular learning approaches, offer both statistical and computational efficiency (Scholkopf & Smola, 2002). We argue that while group averaging fails to produce exactly invariant estimators within a computationally efficient time frame, alternative algorithms can generate invariant estimators for the kernel regression problem in time that is polylogarithmic in the size of the group. In other words, we demonstrate that it is possible to achieve an invariant estimator that is both com-
etry and spectral theory, and cast it as infinitely many convex quadratic programs with linear constraints, for which we derive an efficient solution in terms of time complexity. We trade off computational and statisti- cal complexity by controlling the number of convex quadratic programs solved to obtain the estimator.
We introduce the first polynomial algorithm for learn- ing with invariances in the general setting of kernel regression over manifolds.
putationally efficient and exhibits strong generalization. At first glance, this result may seem counterintuitive and even impossible, since it implies that enumerating all possible invariances is not required to design statistically efficient learning algorithms. This provides theoretical support for the empirical observation that computational efficiency and attainable in learning with invari-
2. Related Work
Generalization bounds and sample complexity for learning with invariances have been extensively studied, particularly in the context of invariant kernels. Works such as Elesedy (2021), Bietti et al. (2021), Tahmasebi & Jegelka (2023), and Mei et al. (2021) provide insights into this area. Ad- ditionally, studies on equivariant kernels (Elesedy & Zaidi, 2021; Petrache & Trivedi, 2023) further our understanding of how equivariances affect learning. PAC-Bayesian meth- ods have also been applied to derive generalization bounds under equivariances (Behboodi et al., 2022). More recently, Kiani et al. (2024) explored the complexity of learning un- der symmetry constraints for gradient- based algorithms. For studies on the optimization of kernels under invariances, see Teo et al. (2007).
strong generalization ances. To the best of our knowledge, this is the first algo- rithm that is both statistically and computationally efficient for learning with invariances in the kernel setting,
Learning with invariances can be formulated as a nonconee optimization problem, which is not tractable directly. To design an efficient algorithm, we leverage the spectral the- ory of the Laplace- saplace-Beltrami operator on manifolds. Notably, since this operator commutes with all (isometric) group actions on the manifold, it is possible to find an orthonor- mal basis of Laplacian eigenfunctions such that each group action on the manifold acts on the eigenspaces of the Lapla- cian via orthogonal matrices. This theoretical framework allows to reformulate the original problem of learning with invariances manifolds as an infinite collection of finite-dimensional convex quadratic programs-one for each eigenspace- eeens constrained by linear conditions. By trun- cating the number of quadratic programs solved, we can efficiently approximate solutions to the primary noncon- vex optimization problem, thereby approximating kernel solutions to the problem of learning with invariances. This reformulation not only enables to derive a polynomial- time algorithm for kernel regression under invariances, but it may also have broader applications, the exploration of which we defer to future research.
A variety of methods have been proposed enhance the per- formance of kernel-based learning models. One prominent approach is the use of random feature models (Rahimi & Recht, 2007), which approximate kernels using randomly se- lected features. Low-rank kernel approximation techniques, such as the Nyström method (Williams & Seeger, 2000; Drineas et al., 2005), have also been proposed reduce the computational complexity of kernel methods; see also Bach (2013); Desa-Bianchi et al. (2015). Divide-and-conuuer al- gorithms offer another pontential avenue for kernel approxi- mation (Zhang et al., 2013). Additionally, the impact of ker- nel approximation on learning accuracy is well-documented in Cortes et al. (2010).
Our work focuses learning with invariances, which dif- fers significantly from the tasks of learning invariances and measuring them in neural networks. For example, Benton et al. (2020) address how neural networks can learn invari- ances, while Goodfellow et al. (2009) study methods to measure the degree of invariance in network architectures. Moreover, this paper, we assume that the invariances in the formulation are given a priori, meaning that the problem of identifying the appropriate group of invariances in the andaor verifying the assumption of invariance-is to be treated as a separate and independent task. For further discussion on testing and learning invariances from data, see Soleymani et al. (2025).
Finally, we emphasize again that this work is cen- tered on achieving exact invariance, as many applica- tions--specially neural networks with strong empirical performance- are explicitly designed to incorporate exact invariances by construction. In summary, this paper makes the following contributions:
We initiate the exploration of statistical canistiall-cmmputationnnll trade-offss in the context of learning with exact invari- ances, focusing specifically on kernel regression.
We reformulate the problem of learning under invari- ances in kernel methods, leveraging differential geom-
Invariance in kernel methods not limited to group averag-
2

---

Learning with Exact Invariances in Polynomial Time
ing. Other approaches such frame averaging (Puny al., 2022), canonicalization (Kaba et al., 2023; Ma et al., 2024), random projections (Dym & Gortler, 2024), and parameter sharing (Ravanbakhsh et al., 2017) have also been proposed to construct invariant function classes. However, canoni- calization and frame averaging face challenges, particularly concerning continuity, which has been addressed in recent works like Dym et al. (2024).
I (M), which quantifies the quality of the estimation, is defined as:
R(F) E - M(
where the expectation is taken over the randomness of the data and labels.
Given a dataset of size n, finding estimators with minimal population risk can be quite complex, often requiring the resolution of non-convex optimization objectives. However, in scenarios where f E H. with H. C (2MM) being Reproducing Kernel Hilbert Space (RKHS), it is feasible to compute kernel-based estimators with low risk efficiently. Specifically, the Kernel Ridge Regression (KRR) estimator for the RKHS H. = (MM), denoted as fKAR. achieves population risk of R(JKRR) being computable in time (n²)), assuming access to an oracle that computes the kernel associated with the space (Bach, 2024). Note that Sobolev spaces (MM with & > d/2 are RKHS. We refer the reader to Appendices A.8 and A.9 for a detailed review of the KRR estimator and related topics on Sobolev spaces.
In specialized tasks such graphs, image, and pointeloud data, Graph Neural Networks (GNNs) (Scarselli et al., 2008;
Xu et al., 2019). Convolutional Neural Networks (CNNs) (Krizhevsky et al., 2012; Li et al., 2021), and Pointnet (Qi et al., 2017a;b) have demonstrated the effectiveness of lever- aging symmetries. Symmetries have also been successfully integrated into generative models (Biloš & Günnemann, 2021; Niu et al., 2020; Köhler et al., 2020). For broader discussion on various types of invariances and their appli- cations across machine learning tasks, see Bronstein et al. (2017).
O (n=e/(etd/22) while
3. Background and Problem Statement
Notation. We begin by establishing some frequently used notation. Let M be smooth, compact, and boundaryless d-dimensional Riemannian manifold. The uniform distri- bution over the manifold is the normalized volume element corresponding to its metric. We denote the space of square- integrable functions over M by (MM and the space of continuous functions by C(M). Furthermore, H (M) rep- resents the Sobolev space of functions on M with parame- ter s, defined the set of functions with equare-integrable derivatives up to order s. Larger values of correspond to greater smoothness, and it holds that H (M) S C(M) if and only if s > d/2, a condition we will assume throughout this paper. For each n E N, we define [x]] = {1, 2,,,,....,, m).
Learning with invariances. We assume that a finite group G acts smoothly and isometrically* on the manifold M, represented by smooth function @ G x M + .M map- ping the product manifold G x . to M. We employ the notation (gg x) as gz for any g E G and a E M. In a sce- nario of learning under invariances, the regression function f is invariant under the action of the group G, satisfying I' (oz) (x) for each g G and M. Thus, leam- ing under invariances introduces additional requirement: not only must we compute an estimator with minimal pop- ulation risk efficiently, but f must also be invariant with respect to G. This additional condition is often satisfied in neural network applications by constructing networks that are invariant by design, such as graph neural networks.
We use log to denote the logarithm with base 2. We refer to Appendices A.I and A.2 for a quick review of Riemannian manifolds.
In the context of learning with Sobolev kernels, the KRR estimator FKRR is not G-invariant (see Appendix A for more details). Consequently, the KRR estimator cannot provide a solution for learning under invariances. However, with a shift-invariant Positive Definite Symmetric (PDS) kernel" K M + R. one can utilize group averaging to derive new kemee and new RKHS holding only G-invariant
Problem statement. We consider a general learning setup on a smooth, compact, and boundaryless Riemannian man- ifold M of dimension d. Our objective is to identify an estimator f E FF from a feasible space of estimators F C (MMM), based on n independent and uniformly' distributed labeled samples S = { y:) : i E [n]} C (M x R)" drawn from the manifold. Here, the labels yi for i E [m] are produced based on the (unknown) ground truth regression function f* E C(M), meaning that y (x.) + c, for each i E [m). where e,, i E [ni], is sequence of independent zero-mean random variables with variance bounded by o².
"The assumption of isometric action is made for simplicity: the proof can be extended to non-isometric actions using standard techniques in the literature, as discussed in (Tahmasebi & Jegelka, 2023).
'A kernel K .M M + R is termed shift- init--invariant with respect to group G if and only if K ((ga1, g22) = K ((21, 22) for each g E G and 21, x2 E M. Shift-invarian kernels are not necessarily G-invariant, For example, one can show that 11" (M) adopts shift-invariant kernel while still producing non-invariant functions its RKHS. We cover the details in Appendix A.9.
The population risk (or generalization error) of an estimator
We assume uniformity for simplicity, with results extending non-uniform sampling with bounded density.
3

---

Learning with Exact Invariances in Polynomial Time
functions:
G is not required to find statistically efficient G-invariant estimators.
Kine (21, 02)
1 = GG|
Σ (2))1 BEG
Oracles. To characterize computational complexity, first we need to specify the type of oracle access provided for the estimation. Before doing so, we briefly review the spectral theory of the Laplace- Beltrami operator on manifolds. For further details, we refer the reader to Appendix A.
Given that the Sobolev space H' (M) adopts a shift- invariant PDS kernel (Appendix A. one can apply the above method to construct and compute a G-invariant ker- nel (assuming access to evaluating its original kernel.. This indicates that the KRR estimator on Kinv yields an invari- ant estimator for f with a desirable population risk (see (Tahmasebi & Jegelka, 2023) for a comprehensive study).
The Laplace-Beltrami operator generalizes the Laplacian operator to Riemannian manifolds. It has a basis of smooth eigenfunctions Φx,, E (MM. which serve as an orthonor- mal basis for (MM The index À represents the eigenvalue corresponding to the eigenfunction Φxxe. and E [mx] runs over the multiplicity of X, denoted by myx The eigenvalues can be ordered such that 0 = A < X1 S X2 S ..... oc. For example, in the case of the sphere S the spherical harmonics, which are homogeneous harmonic polynomials, are natural choice of eigenfunctions.
However, in terms of computational complexity, this method requires ((n2)G)) time compute the new kernel between pairs of input data. In many practical scenarios, |G] can be intolcrably large. For instance, for the permutation group Pa. we have [G| = d! ~ vd(d)d which is super-exponential in d. Consequently, the group averaging method cannot provide an efficient algorithm for learning with exact invari- ances. We emphasize "exact invariance" here, as the sum involved in Kinv can be approximated by summing over a number of random group transformations. However, this does not guarantee exact invariance, which is the primary goal of this paper.
The sequence of eigenfunctions and their corresponding eigenvalues provide critical information about the geometry of the manifold. In this work, we make use of the following two types of oracles:
Other traditional approaches for achieving learning under invariances include data augmentation, canonicalization, and frame averaging. For data augmentation, we need to increase our dataset size by multiplicative factor of [G], which is often impractical within efficient time constraints. This is because, for any datapoint v; E S, data augmentation requires adding new datapoint gæ; for each group element E G to ensure invariance of the underlying learning pro- cedure in a black-box manner, leading to a complexity of Gn] Canonicalization involves mapping data onto the quotient space of the group action and subsequently finding an estimator (e.g., KRR estimator) on the reduced input space. However, this method is also infeasible for kernels due to the unavoidable discontinuities and con-smoothness of the canonicalization maps, which violate RKHS require- ments (Dym et al., 2024). Finally, frame averaging is anal- ogous to canonicalization, but it remains unclear how to address continuity issues for efficient frame sizes. More- over, it requires careful design of frames tailored the specific problem at hand, making it unsuitable for general- purpose algorithm. Thus, motivated by these observations, we pose the following question:
The ability to evaluate any eigenfunction Φx,e(1)) at a given point E M.
The ability to compute the L2(M) inner product be-
tween a shifted eigenfunction Φx,(gz)) and another eigenfunction Φx,e (z) for any group element E G.
For both oracles, we assume free access as long as Dx == Exer my = poly(n, d)), where D^ denotes the number of eigenfunctions with eigenvalues less than or equal to A. This assumption is motivated by the case of S where spherical harmonics can be efficiently evaluated or multi- plied in low dimensions (in such cases, only a few mono- mials need to be processed, making the task simple*). The first oracle handles the geometric structure of the manifold, while the second oracle captures the relationship between the group action and the manifold's s spectrum.
4. Main Result
In this section, we address the question raised in the previous section by presenting the primary result of the paper, which is encapsulated in the following theorem.
Theorem 1 (Learning with exact invariances in polynomial time). Consider the problem of learning with invariances with respect to a finite group G using a labeled dataset of size n sampled from a manifold of dimension d. Assume that the optimal regression function belongs to the Sobolev space of functions of order s, i.e., f HMM for some
Is it possible obtain a G-invariant estimator for 1* E H*M) with desirable population risk (similar to the case without invariances) in poly(n, d, log( time?
In the next section, we answer this question affirmatively. This is surprising, as it suggests that enumerating the set
*This extends to the Stiefel manifold and tori.
4

---

Learning with Exact Invariances in Polynomial Time
> d/2 and let = 2s/d. Then, there exists an algorithm that, given the data, produces an exactly invariant estimator f such that:
5. Algorithm and Proof Sketch
In this section, we provide a proof sketch for Theorem I, introducing several new notations and concepts necessary for achieving the reduction in time complexity.
It runs in time (log" (log)((G) (IG))n + +
It achieves an excess population risk (or generalization error) of R()) = ((n==/((+4/2))))
We begin with the most natural optimization program for obtaining an estimator: the Empirical Risk Minimization (ERM), which proposes the following estimator:
It requires O( log(1 calls to construct the estimator;
+n(2+a)((1to)) (n oracle
1
n Σ (f(z²) y1)² J
FERM- = arg min (EH
n
For any x M, the estimator f(xx can be computed in time O Onn using On (n)) oracle calls.
where S {(
[n]] S (M x R)" denotes the
sampled (labeled) dataset.
However, as discussed, this method does not necessarily produce an estimator that is exactly invariant. A natural idea is to introduce group invariances as constraints into the above optimization, leading to the following constrained ERM solution:
The full proof of Theorem is presented in Appendix B.3, while a detailed proof sketch is provided in Section 5, and the algorithm is outlined in Algorithm 1.
Let us interpret the above theorem. Note that without any in- variances, the Kernel Ridge Regression (KRR) estimator (de- tails are given in Appendix A.9) provides an estimator fKRR for the Sobolev space H* HMM that is computed in time (n²)) and achieves the risk R((KRR)
iRRM-C = arg min (EH-(M)
n Σ (f(x)) n1)² -v)² "
1
==((std///)) which is minimax optimal. Here, while KRR cannot guar- antee an exactly invariant estimator, we propose another estimator which is both exactly invariant and also converges with the same rate ((==</(+d//))). As a result, we achieve exact invariances with statistically desirable risk (or sample complexity). In other words, the population risk is the same as the optimal case without invariances, which shows that the algorithm introduces no loss in statistical performance while enforcing group invariances.
s.t. V(g,z) M: f(gx)= - f(x).
While this formulation ensures exact invariance, it intro- duces |G] functional equations. This problematic for two reasons: first, [G] constraints are prohibitively many, and second, these constraints require solving functional equalities, which are not easily achievable. Moreover, the functional equations involve non-linear (pointwise) con- straints on the estimator function, which at first glance appear intractable due to nonconvexity of the contraints f f(gz) = f(x) for general choice of g.
We thus come to the following conclusion:
Therefore, it is necessary reformulate the above optimiza- tion program. The goals of the reformulation are to reduce the number of constraints and encode the functional equa- tions into more tractable constraints, ideally linear ones.
The problem of learning with exact invariances can be efficiently solved in time poly (n, d, log((G])) and with excess population risk (or generalization error) =/(++/222) which is the same statistical performance as for learning without invariances.
Reducing the number of constraints. We begin by using the following basic property (based on the group law):
(vg {91,92).V M: f(gz) = f(x))
worth mentioning that, according to the theorem, the proposed estimator f is not only efficiently achievable but also efficiently computes new predictions on unlabeled data.
(ar E (: = f(t)
This observation allows us to eliminate many unnecessary constraints. Specifically, we only need constraints over a small subset of G if this subset can generate any group ele- ment through arbitrary group multiplications. To formalize this, we introduce the following definition:
Remark 1. We notice that in the proof of Theorem I, the actual time and sample complexity depends only on the size of the minimum generating set of the group G, denoted by p(G), instead of log( Gl). We use the logarithm in the theo- rem just to make the improvement from the naive approach clearer. The actual proof allows to achieve the tighter result with (G) & log((G)), which holds for any finite group (see Proposition B.1 in Appendix I).. Note that for some cases (such as cyclic groups) ((G) < log()G)).
Definition 5.1. A finite group G is said to be generated by subset S C G if for every g E G. there exists a sequence of elements $1 $2,...... Sp such that for each E [M]. either s; E or s; E S and g = 8182 ... Sk. The minimum size of such a subset is denoted by P(G).
5

---

Learning with Exact Invariances in Polynomial Time
Clearly, P(G) < [G]. However, it can be shown (see Ap- pendix B.I) that p(G) I log(IG)), which represents
coefficients at a certain cutoff frequency X, which allows the problem to be parametrized with finitely many parameters. Although this introduces bias into the estimation (since eigenfunctions will not be captured), the bias is bounded by the above inequality for Sobolev spaces.
exponential improvement over the trivial upper bound.
Thus, we can reformulate the constrained ERM as:
SERM-C- = arg min (EH)(M)
(f(a.) u)²
Interestingly, this spectral approach yields a more meaning- ful optimization problem when considering the population risk function rather than ERM. The population risk, which is the primary objective in regression, is given by:
s.t. V(g ES M: f(gx)= - f(x),
where |S| S log( This way we reduce the number of constraints from |G] to log((G') by leveraging the concept of minimal group generators. Note that this fact cannot be directly used in data augmentation, group averaging, or canonicalization techniques.
R()) = Es [IVS- S M[ = ΣΣ t=
B[U S2
Constrained spectral method. To review, we introduced efficient way to impose the constraints related to group invariances in the ERM objective and later presented spec- tral methods for obtaining estimators. The last step here is to combine these to achieve exact invariances via a con- strained spectral method. We use an important property of the Huplace-Beltrane operator to introduce the algorithm.
Optimization in the spectral domain. The constrained ERM formulation presented above, while advantageous in terms of reducing the number of constraints, involves opti- mizing over the dimenie-dimeiiinall space (MM) which is computationally intractable. One way to make this prob- lem tractable is to parametrize the estimator and search for the optimal parameters. To achieve this, we utilize the spec- tral theory of the Laplace-Beltrami operator over manifolds. While detailed discussion of spectral theory is provided in Appendix A, we summarize the relevant concepts here.
Let AM denote the Laplace- Laplace-Beltrami operator the man- ifold M, and let G be group acting isometrically on M. Define the linear operator T, : f(z) + fgr) for each group element g E G and any smooth function f on the manifold. Then, we have
As mentioned earlier, the Laplace-Belramii operator yields a sequence of orthonormal eigenfunctions Φx.e E (2MM), ))
AM = (o))m(()),
where x E (Ao, ... S [0, x)) represents the eigenvalue corresponding to the eigenfunction éx,e, and E [mx] indexes the multiplicity of x, denoted by max Therefore, any estimator f (MM can be expressed as:
for any smooth function e on the manifold (for a formal proof, please refer to Appendix A.5).
This identity tells us that the Saplace-Beltramt operator AM commutes with the operator T, for each Since both operators are linear, spectral theory implies that the commutativity shows the eigenspaces of AM are preserved under the action of the group G. meaning the operators can be simultaneously diagonalized. Specifically, for any X, and any g G, the function (xx) is linear combina- tion of eigenfunctions Φx,e, l' E [mx]. In particular, the group G' acts via orthogonal matrices on the eigenspace Vx == span(ox. : f E [mx]) for each A.
f(x)= = Σ MEΣNE (z)) fae= (f.Adiim))
The idea is to parametrize the problem by finding the best coefficients fx.e. However, since there are infinitely many cigenvalues, there are infinitely many parameters estimate, which is not feasible in finite time. Fortunately, we know that 1 E H (M). From the definition of Sobolev spaces (see Appendix A.8), we have:
Let (g) denote the m. x m. orthogonal matrix corre- sponding to the action of an element g E G on Vx for each x. Then, function
my
f(x) = Σ ΣDR fx.es.e(z)
where D2 = Exx my, and a = 24 1.
d'
2=1
Thus, we conclude that:
is G-invariant if and only if
my
Σ
Σ DI00)
Da(g)f= Vg AgEGYX AI.,
D=
where fa = (fx))e(( E RM for each A. We can further reduce the number of conditions by passing G to a generator set, which gives only log([G)) conditions.
for any D >>0 0. This shows that for Sobolev regression functions f E HMM), we can truncate the estimation of
6

---

Learning with Exact Invariances in Polynomial Time
Thus, the commutativity of the Banllac-Belttrmii operator and any isometric group action allows us introduce only linear constraints on the spectral method to achieve exact invariances. This leads to the following optimization pro- gram:
where i denotes Moore-Penrose inverse.
The final estimator of the algorithm is given by
{())= = E Σ fxe
A:DASD
A ΣΣ B[(A2=- - JZ,e) min Fa.t
This meta approach to design a G-invariant estimator î from any primary estimtor novel and may be of inde- pendent interest. Pseudocode for the method is presented in Algorithm 1. Since the invariance is imposed in the spec- tral representation, we refer to our proposed algorithm as Spectral Averaging (Spec-Avg).
2=1
s.t. AA SYAA
D = fx
Here, fū, E, = Enylyox. is not known a priori; only n samples (Ii Ub) E M x R.i E [n]] are given. Furthermore, the constraints are independent for different eigenspaces (i.e., different A), and the objective is sum over eigenspaces. This means can decompose the problem into set of linearly constrained optimization programs, one for each eigenspace Vx:
Algorithm 1 Learning with Exact Invariances by Spectral Averaging (Spec Avvg)
Input: $ 8= Mk) E [n]] and a 22/d E (1, oo).
Output: f(x).
T
1: Initialize D f- n1((1a)))
min
Bl(fae- 1x,e)²,
2: for each À such that Dx < do
3: for each & E [mx] do
s.t. S (* = fx-
4: Fx.e x 1
n E. (x)))
5: end for
This reformulation allows us to propose efficient estimators for the problem.
6: end for
7: for each À such that Dx S do
8: Solve the following linearly constrained quadratic
Empirical estimator: In this paper, we suggest the follow- ing auxiliary empirical mean estimator from the data for the above optimization program on Vx:
program over my variables:
1723
FA, arg min
(fsee-
n FA
1 Σ (o))) ve [mx]. n
(1)
Ix
Emll
s.t. V: D* = -a--
Moreover, stop estimation and set Fx,e O when
9: end for 10: Return: f(x) = EXDAeD Em Preere())
Dx > D, where D is a hyperparameter. To obtain a G- invariant estimator from our primary estimator, we solve the following quadratic program to find a solution satisfying the constraints for each VA with DA I D:
We conclude this section by reviewing how we apply the results from Algorithm the two following important examples.
fx.E= == arg min
[uSe - JxA)?, 2=1
Example 5.2. Consider the problem of learning under in- variances over the unit sphere 5ct-1 = {ar E TRd, || }}. where the group G' is the group of all permutations of coordinates. Note that |G] = d!, which is prohibitively large for data augmentation or group averaging. However, this group is generated by only two elements: σ1 = (12) and 02 = (12 ... d). Here, a swaps the first and second coordinates, while da is a cycle that maps 1 + 2, 2 3. and so on, cyling with d 1.
Jx.e
s.t. Vge S: (*) fx
This optimization problem is a convex quadratic program with linear constraints that can be solved iteratively using the rich convex optimization machinery. Additionally, it has closed-form solution as noted in Proposition B.2 in Appendix B.2. Let Bd E RIS|m,, Xm be defined as the augmented matrix resulting from concatenating D (g) for all g S, i.e., Bd (D> T)T, (D> T)T...., (D)(s))) - TT. Then,
The eigenspaces VA for the sphere are precisely the sets of homogeneous harmonic polynomials of degree k where
X = k(k + d - 2). The permutation group acts on V,, by permuting the variables of the polynomials. This action is clearly linear, and the matrices D*) can be efficiently
BA- Jx.- BA (ABBBBBAT (B-
7

---

Learning with Exact Invariances in Polynomial Time
computed (using tensor products) long k is small. Moreover, homogeneous polynomials of degree k can also be computed efficiently for small k. This shows that the oracles considered in this paper align perfectly with what we observe in the important case of spheres and polynomial regression. In Algorithm I, we first compute the coefficients of each polynomial for degree k, up to a small k, and then solve a quadratic program with only two linear constraints to obtain an exactly invariant polynomial solution.
lation facilitates the analysis of KRR and Spec-Avg Avg under symmetry constraints, ensuring their compatibility with the underlying group structure. It is worth noting that, in this setting, |G] = 2 Consequently, group averaging is com- putationally inefficient due to the exponential growth of the group size with the dimensionality d.
6.2. Settings
We conduct our experiments for d = 10. The trained models are evaluated on test dataset of size 100. Both the test and train datasets are generated uniformly from the interval [-1, 1] independently and identically distributed. Each point in our plots represents average over 10 different random seeds (from 1 to 10) to account for the randomness in the data generation process.
Example 5.3. Consider the same setup as the previous ex- ample but assume d = 2, i.e., the manifold is the unit circle. In this case, each eigenspace VA is spanned by sin(kf) and cos(k where À = AP.. Let us assume our task is to find an estimator invariant with respect to rotations by integer multiples of 2x. This group is cyclic and is generated [G]
[ Thus, we have only one constraint for each eigenspace. Indeed, one can observe that D* (go) = R(k ( where R(.) E 1_2x is the two- dimensional rotation matrix. Thus, this example further illustrates how our oracles are defined to solve the problem.
by only one element go
2xt
6.3. Results
The results of the experiments are depicted in Figure I and Figure 2 in Appendix C. While our algorithm (Spec-Avg) is G-invariant by construction, there is no theoretical guaran- tee for Kernel Ridge Regression (KRR) to be G-invariant. In Figure I in Appendix C, we demonstrate that this is indeed the case in practice, as the estimator KRR is not G-invariant. We define the following measure of Invariance Discrepancy:
6. Experiments
In this section, we provide complementary experiments to support our theoretical results. We first show that, in practice, Kernel Ridge Regression (KRR) is not a G- invariant estimator. Then, we demonstrate that our algo- rithm (Spec-Avg) achieves the same rate of population risk as KRR, while enjoying exact invariance properties.
ID( del sup .EX.GEG
1f(x) - f(gx)),
where f is the estimator. We report this value for KRR across different choices of the regularization parameter A. It is worth noting that IF( is zero for the Spec-Avg estimator, as G-invariant by design.
6.1. Problem Statement
We consider the input space (manifold) T = 1-1, 1)d, which represents a flat d-dimensional torus. Additionally, we consider the group of sign-invariances G = {+1]a, acting on this space via coordinate-wise sign inversions. The dataset is generated as n independent and identically distributed di.i.d.) samples drawn uniformly from this space, with the target function defined as: f*x) = > ix?.
In Figure 2 in Appendix C, we present the empirical ex- cess population risk of KRR and Spec-Avg for different hyperparameters À and D, respectively. As expected, it is demonstrated that with an appropriate choice of hyperpa- rameters, KRR and Sppec-Avg achieve the same order of test error. Higher values of the regularization parameter À for KRR correspond lower values of the sparsity parame- ter D for Spec-Avg, both of which act mechanisms for regularizing the norm of the estimator. It can be observed that Spec-Avq with D = 176 achieves the same order of performance as KRR with À = 50.
Clearly, this function is invariant w.r.t. group action G. To analyze estimation via kernels in this setup, we consider periodic kernel on the torus T specifically the von Mises Kernel (von Mises, 1918; Mardia & Jupp, 2009), defined as: (T, y)= = exp (77 cos(T( - -))), where is a positive parameter associated with kernel bandwidth. This kernel function particularly useful for circular and directional statistics.
7. Conclusion
In this paper, we explore the statistical computatoooonnt trade- offs in learning with invariances, focusing on kernel regres- sion. We observe that while the Kernel Ridge Regression (KRR) estimator can address this problem, it is not invariant without group averaging, and since group averaging is costly for large groups, we ask whether it is possible to develop statistically sound estimators with efficient time complexity.
Moreover, the kernel admits the following sign-invariant eigenfunctions: dh,, de.........ea (x()) (x) = II ( where 4, E N U (0). The corresponding eigenvalues can be com- puted as À = x Σ'= L, derived from the partial differen- tial equation A Adi, + d = O. This formu-
8

---

Learning with Exact Invariances in Polynomial Time
Our findings show that by reformulating the problem and reducing the number of constraints using group laws, we can express it as solving an infinite series of quadratic opti- mization programs under linear constraints. We conclude with an algorithm that achieves an exactly invariant estima- tor with polynomial time complexity and highlight several additional questions for future research.
ing computationall-sttisiiea trade-off's in other estimation problems with invariances such as density estimation (Chen et al., 2023; Tahmasebi & Jegelka, 2024) could serve as compelling avenue for future research.
A Acknowledgments
AS and PJ are partially supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme AISG Award No: AISG2-RE RP- 2020-018, 8, and by the Office of Naval Research (ONR) grant N00014-24 -1-2470. BT and SJ are supported by the Office of Naval Research under grant N00014-20- 1-0-200-12222 1-2023 (MURI ML-SCOPPE), the National Science Foundation under award CCF-2112665 (TILOS AT Institute), and an Alexander von Humboldt Professorship.
8. Discussion and Future Directions
We initiated the study on computationallstatisiisss trade- off's in learning with exact invariances. We designed an algorithm that shows achieving the desirable population risk (the same as kernel regression without invariances) in poly(n, d, log((Gl)) time for the task of kernel regression with invariances on general manifolds. We note that, for sim- plicity, we have focused on boundaryless manifolds and iso- metric group actions. However, using standard techniques, the theory can be extended to more general cases as well'. While the proposed spectral a algorithm is computationally efficient, it does not offer any improvement in sample com- plexity over the baseline R() = On (m==//<+d//2) It has been observed that without computational constraints, better convergence rates are possible for learning with invariances (Tahmasebi Jegelka, 2023), which are minimax optimal. Thus, it remains open whether those improved rates are achievable in poly(n, d, log(lG))) time.
Impact Statement
The primary focus of this work is on theoretical problems in machine learning, specifically learning with invariances. As such, it does not have direct societal implications or ethical concerns.
References
Bach, F. Sharp analysis of low-rank kernel matrix approx- imations. In Conference on Learning Theory (COLT),
We note that the oracle access we assumed is primarily motivated by the case of the sphere, where polynomials can be evaluated, multiplied, composed by group elements, and integrated efficiently when they are of relatively low degree. We believe this is the most natural oracle access for this problem, it aligns well with applications involy- ing polynomials. An interesting future work could be to trade-offs using al-
2013. 2
Bach, F. Learning theory from first principles. MIT press, 2024. 3
Batzner, S., Musaclian, A., Sun, L., Geiger, M., Mailoa, J. P., Kornbluth, M., Molinari, N., Smidt, T. E., and Kozinsky. B. E(3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 13(1):2453, 2022. 1
investigate the aatiitical-computate ternative oracles, c.g., similar to the kernel trick, how to design computationally efficient algorithms that have only access to the inner product the RKHS. Another interesting future direction is to find whether random feature models as approximations for kernels can significantly improve the trade-off of learning with invari- ances. At present, our theory does not apply to random feature models.
Batzner, S., Musaelian, A., and Kozinsky, B. Advancing molecular simulation with equivariant interatomic poten- tials. Nature Reviews Physics, 5(8):437 438.. 2023. 1
Behboodi, A., Cesa, G., and Cohen, T. S. pac- bayesian generalization bound for equivariant networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 2
We also observe that the spectral algorithm used in this pa- per does not employ the kernel trick, as it requires access to the entire set of features, rather than just their inner products. An interesting question is whether it is possible to utilize kernel tricks and find an alternative (polynomial-time -imme) algo- rithm for learning under invariances. This approach could potentially improve the statistical efficiency of the spectral algorithm. In the end, we would like to note that captur-
Benton, G., Finzi, M., Izmailov, P., and Wilson, A. G. Learn- ing invariances in neural networks from training data. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 2
Bietti, A., Venturi, L., and Bruna, J. On the sample complex- ity of learning under geometric stability. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
See c.g., Tahmasebi & Jegelka (2023).
2
9

---

Learning with Exact Invariances in Polynomial Time
Biloš, M. and Günnemann, S. Scalable normalizing flows for permutation invariant densities. In Int. Conference Machine Learning (ICML), 2021.
Goodfellow, I., Lee, H., Le, Q. Saxe, A., and Ng, A. Mea- suring invariances in deep networks. In Advances in Neural Information Processing Systems (NeurIPS), 2009,
2
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Van- dergheynst, P. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 18 18-42, 2017. 1,3
Grisafi, A., Wilkins, D. M., Csányi, G., and Ceriotti, M. Symmetry-adapee adapted machine learning for tensorial proper- ties of atomistic systems. Physical review letters, 120(3): 036002, 2018.
Canzani, Y. Analysis on manifolds via the laplacian. Lecture Notes available at: http://www. math. harvard. edulcamaanittor///pppaaaaa pdf. pp. 41-44, 2013. 15
Hinton, G. E. Learning translation invariant recognition in a
massively parallel networks. In International conference on parallel architectures and languages Europe, pp. 1-13. Springer, 1987. 1
Cesa-Bianchi, N., Mansour, Y., and Shamir, O. On the complexity of learning with kernels. In Conference on Learning Theory (COLT), 2015. 2
Hörmander, L. The spectral function of an elliptic opera- tor. In Mathematics Past and Present Fourier Integral Operators, pp. 217-242. Springer, 1968. 15
Chavel, I. Eigenvalues Riemannian geomeiry. Academic press, 1984. 14
Kaba, S.-O., Mondal, A. K., Zhang, Y., Bengio, Y., and Ravanbakhsh, S. Equivariance with learned canonicaliza- tion functions. In Int. Conference on Machine Learning (ICML), 2023. 3
Chen, Z., Katsoulakis, M., Rey-Bellet, L.,, and Zhu, W. Sam- ple complexity of probability divergences under group symmetry. In Int. Conference on Machine Learning (ICML), 2023. 9
Cortes, C., Mohri, M., and Talwalkar, A. On the impact of kernel approximation on learning accuracy. Int. Con- ference on Artificial Intelligence and Statistics (AISTATS), 2010. 2
Kiani, B., Le, T., Lawrence, H., Jegelka, S., and Weber, M. On the hardness of learning under symmetries. In Int. Conference on Learning Representations (ICLR), 2024.
Köhler, J., Klein, L., and Noé, F. Equivariant flows: exact likelihood generative learning for symmetric densities. In Int. Conference on Machine Learning (ICML), 2020. 3
Díaz, M., Drusvyatskiy, D., Kendrick, J., and Thomas, R. R. Invariant kernels: Rank stabilization and generalization across dimensions. arXiv preprint vrXiv:2502.01886 2025. 1
Kondor, R. Group theoretical methods in machine learn- ing. Columbia University, 2008. 1
Drineas, P., Mahoney, M. W., and Cristianini, N. On the nyström method for approximating gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 2005.
Krizhevsky, A., Sutskever, I,, and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2012. 3
Dym, N. and Gortler, S. Low now-dimensional invariant em- beddings for universal geometric learning. Foundations of Computational Mathematics, pp. 1 1-41, 2024.
Lee, J. Introduction to Smooth Manifolds, volume 218. Springer Science & Business Media, 2012. 12
Dym, N., Lawrence, H., and Siegel, W. Equivariant frames and the impossibility of continuous canonicaliza- tion. In Int. Conference on Machine Learning (ICML),
Lee, J. M. Riemannian manifolds: an introduction to curva- ture, volume 176. Springer Science & Business Media, 2006. 12
2024. 1, 3,
Li, Z., Liu, F., Yang, W., Peng, S., and Zhou, J. A survey of convolutional neural networks: analysis, applications, and prospects. IEEE transactions on neural networks and learning systems, 33(12):6999-7019 2021. 3
Elesedy, Provably strict generalisation benefit for invari- ance kernel methods. In Advances in Neural Informa- fion Processing Systems (NeurIPS), 2021.
Elesedy, B. and Zaidi, S. Provably strict generalisation benefit for equivariant models. Int. Conference on Machine Learning (ICMI), 2021.
Ma, G., Wang, Y., Lim, D., Jegelka, S., and Wang, Y. A can- onization perspective on invariant and equivariant learn- ing. arXiv preprint MxXiv:2405.83777 2024. 3
Evans, L. C. Partial differential equations, volume 19.
Mardia, K. and Jupp, P. E. Directional statistics. John Wiley & Sons, 2009. 8
American Mathematical Society, 2022. 14
10

---

Learning with Exact Invariances in Polynomial Time
Mei, S., Misiakiewicz, T., and Montanari, Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021. 2
Sogge, C. D. Concerning the ip norm of spectral clusters for second-order elliptic operators compact manifolds. Journal of functional analysis, 77(1):123-133) 1988. 15
Myers, S. and Steenrod, N. E. The group isometries of riemannian manifold. Annals of Mathematics, 40(2): 400-416, 1939. 14
Soleymani, A., Tahmasebi, B., Jegelka, S., and Jaillet, P. A robust kernel statistical test of invariance: Detecting subtle asymmetries. In Inf. Conference Artificial Intel- ligence and Statistics (AISTATS), 2025. 2
Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. In Int. Conference Machine Learning (ICML), 2020. 3
Tahmasebi, and Jegelka, S. The exact sample complexity gain from invariances for kernel regression. In Advances
Neural Information Processing Systems (NeurIPS), 2023. 2, 3, 4, 9, 15, 16
Palais, R. On the differentiability of isometries. Pro- ceedings of the American Mathematical Society, 8(4): 805-807, 1957. 14
Tahmasebi, B. and Jegelka, Sample complexity bounds for estimating probability divergences under invariances. In Int. Conference on Machine Learning (ICML), 2024.
Petersen, P. Riemannian geometry. Graduate Texts in Matheematicx/Springrr--eeee Verlarr, 2006. 12,
Teo, C.., Globerson, A., Roweis, S., and Smola, A. Con- vex learning with invariances. Advances in Neural Information Processing Systems (NeurIPS), 2007.
Petrache, M. and Trivedi, S. Appeaiiaaioongnnnallaaaiiioo trade-offs under (approximate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
generalization
Unke, O., Bogojeski, M., Gastegger, M., Geiger, M., Smidt, T,, and Müller, K.-R. Se(3)-equivariant prediction of molecular wavefunctions and electronic densities. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 1
Puny, O., Atzmon, M., Bem-Hamu, H., Misra, I., Grover, A., Smith, F. J., and Lipman, Y. Frame averaging for invari- ant and equivariant network design. In Int. Conference Learning Representations (ICLR), 2022. 3
von Mises, R. Über die "ganzzahligkeit" der atomgewichten und ververwandte fragen. Physical Journal, 19:490, 1918. 8 Williams, C. and Seeger, M. Using the nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), 2000. 2
Qi, C. R., Su, H., Mo, K., and Guibas, L. Pointnet: Deep learning on point sets for 3d classification and segmen- tation. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2017a.
Qi, R., Yi, L.,, Su, H., and Guibas, Pointnet+++: Deep hierarchical feature learning on point sets metric space. In Advances Neural Information Processing Systems (NeurIPS), 2017b. 3
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How pow- erful are graph neural networks? In Int. Conference on Learning Representations (ICLR), 2019.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
Zhang, Y., Duchi, J., and Wainwright, M. Divide and con- quer kernel ridge regression. In Conference Learning Theory (COLT), 2013.
Ravanbakhsh, S., Schneider, J., and Poczos, B. Equivari- ance through parameter-sharing In Int. Conference on Machine Learning (ICML), 3017.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Scholkopf. B. and Smola, A. J. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Smidt, T. E. Euclidean symmetry and equivariance in ma- chine learning. Trends in Chemistry, 3(2):82-85, 2021.

---

Learning with Exact Invariances in Polynomial Time
A. Background
A.1. Riemannian Manifolds
In this section, we review some fundamental definitions from differential geometry and refer the reader to Lee (2006); Petersen (2006); Lee (2012) for further details.
Definition A.1 (Manifold). A topological manifold M of dimension dim(MM) is completely separable Hausdorff space that is locally homeomorphic to an open subset of Euclidean space of the same dimension, specifically Rdim(M), More formally, for each point .,, there exists an open neighborhood U C CM and a homeomorphism & U + Ü, where Ü S (
The value dim(MM is referred to as the dimension the manifold. Examples of manifolds include tori, spheres, IR and graphs of continuous functions. Manifolds with boundaries differ from boundaryless manifolds in that they may have neighborhoods that locally resemble open subsets of closed -immenindee upper half-spaces, denoted as HHddm((MM) C [ddim(M) defined as follows:
H (2,1, 22......... ma)
R
Zd 2 03.
Definition A.2 (Local Coordinates). Given a chart (U, 6) -) pair consisting of local neighborhood U and the corresponding homeomorphism Φ U + -o a manifold M with dimension d, we define local coordinates (ar), x? .x?.....""" such that
..
(p) = (p). ( ,,,
for each point p U.
Definition A.3 (Tangent Space). At each point E M, the tangent space T.M is defined as the vector space formed by the tangent vectors to the manifold M at æ. A tangent vector v E T,M can be represented as the derivative of a smooth curve (t) (-e,e) + .M defined on the manifold with the property that (0) = æ. It is expressed as
d == dt (1)
The tangent space T.M is real vector space with dimension dim(M).
Definition A.4 (Riemannian Metric Tensor). A Riemannian metric tensor 3 on a manifold M a smooth inner product defined on the tangent space T.. at each point x E M. For any two tangent vectors u, E T,M, the metric assigns a real number 9 u, v) E R.
Definition A.5 (Riemannian Manifold). A Riemannian manifold is defined pair (M, g), where M is manifold and g is Riemannian metric tensor defined on the tangent space T&M each point M.
A Riemannian metric tensor provides essential tools for the study of manifolds, which we formalize below. It enables the following:
the definition of the geodesic distance d(x, v) between any two points x, y M on the manifold,
a volume element d volly over the manifold, serving as the measure for the Borel sigma-algebra over open subsets of the manifold M, and
the measurement of the angle between any two tangent vectors u, v E T,M, which in turn provides the size of tangent vectors.
Definition A.6 (Geodesic Distance). The geodesic distance d. (2,xx)) 8) between any two points x, E M on the manifold defined as the infimum length among all smooth curves 7 [0, M connecting x to y (7(0) = x, 71) y). The length of curve y is defined as
L(7) L'' V9rco 4t,
where v denotes the derivative dr di
"This notation differs from g, which denotes group elements.
12

---

Learning with Exact Invariances in Polynomial Time
Definition A.7 (Volume Element). The volume element dvolg(4) on Riemannian manifold (M,g) is defined
dvolg = ddet(gs) dx' dx² A ... A dx".
where gry are the components of the Riemannian metric tensor, (x) x² ,..., x") are the local coordinates, and denotes the exterior product.
The volume element provides way compute the volume of subsets of M by integrating functions over M. Moreover, Borel measure μ open subsets of M can be derived form the volume element to form probability measure space, e.g., uniformly over the manifold.
Definition A.8 (Smooth Map). A maping f M - N is smooth map if for any charts (U, の) M, and (V, b) N, the composition function v o f o foolll [M)i(MM + diim()) is infinitely differentiable.
Definition A.9 (Pullback of the metric tensor). Given Riemannian manifolds M, (W. and p M + W a smooth map between them. The pullback of the metric tensor g by o, denoted by 40 g is the Riemannian metric tensor on manifold M defined by.
(4'0)) (1, v)) = 9e(a) (d (u), (v))..)) for all points x E M and all u T,M,
where dip. TTM + No Vin is the differential of the map y at point
Thus, the pullback metric y0g M captures the relation between tangent vectors of M in terms of how they mapped to the manifold N via yp.
Definition A.10 (Connected Manifold). A manifold M is connected if for any points x, x' M, there is smooth curve 7: [0, 1] + M such that (0) and ((1) = x'.
Throughout this paper, we focus on smooth, connected, compact and boundaryless Riemannian manifolds (M, g) unless stated otherwise. For a Riemannian manifolds (M, we denoted the dot product induced by the metric tensor g as (u, u) = 9u, (u. u) for all u, v E Tz. We drop the subscript x whenever it is clear from the context.
A.2. Functional Spaces over Manifolds
Now equipped with probability measures on manifold discussed in Appendix A. we are ready to define functional spaces (MM and Sobolev spaces H- (M) on manifold M analogously to their Fuclidean counterparts in the following,
Definition A.11 (Functional Spaces on Manifolds). The Lebesgue functional spaces (*M for E [1, oo]. and the Sobolev spaces H (M) for 2 0 on a smooth Manifold M, are defined as follows:
The Lebesgue space (P()) consists of measurable functions f :M - IR such that ([fller(M) < oo where,
(Jm ( [f(z)) du(x)) less [((r) < 00.
if E (1) if = 00
|
where μ is the uniform measure over the manifold M.
The Sobolev space H² (MM consists of measurable functions whose derivatives up to order are in L22 i.e.,
(MM = L D L2( for all multi iulti-indices a with |a| < s).
A.3. Lie Group of Isometry Maps
In this section, first we state basic definition of isometric mappings over manifolds and then wrap up by characterizing the isometry group over the manifold.
Definition A.12 (Isometry Map). A bijective mapping T .M- - -M is an isometry on the manifold (G, (f.g) = d'x.
We also state a brief definition of Lie groups for completeness.
13

---

Learning with Exact Invariances in Polynomial Time
Definition A.13 (Lie group). A group G is Lie group with smooth group operations (multiplication and inversion) if it is additionally smooth manifold.
The space of bijective Riemannian isometries defined on the manifold (M, g). denoted by ISO(M,,)) constitutes group with composition operation. The celebrated Myers- Myers-Steenrod theorem states that any isometry map E ISO g) between connected manifolds an isometry (Myers & Steenrod, 1939; Palais, 1957). Myers & Steenrod (1939) took it step further and proved that isometry group of a Riemannian manifold (M, g) is a Lie group.
Alternatively, ISO(M, g) can be charecterized by the pullback the metric tensor. terms, T E ISO(M..)) if and only g g'g (Petersen, 2006).
A.4. Laplacian on Manifolds
In this section, we reiterate over definition of Laplace-Beline Beltrami operator on manifolds (which is the generalization of the Laplacian operator A 0f + 03 + +....... 03 defined on the Euclidean space Fd)) and state several interesting properties that will utilize later. We refer Chavel (1984) for additional details.
Definition A.14 (Laplace-BBe Belltami operator). Given Riemannian manifold (M,g), the Kaplace-Beltrant operator A HMMM) + H- HMM) acts smooth function f .M - IR by
Agf = div (ivy(grad,())))
Moreover, Agf has an equivalent weak formulation (Evans, 2022), the unique continuous linear operator 4, HMM (M (M) which is solution to the equation.
JAx (()))))())) / (Vob(a),, doll,() o, V.
HMM.
(2)
The Laplace-Beltrami Beltrami operator Ag is self-adjoint, cliptic and diagonalizable in LP(M) (Chavel, 1984; Evans. 2022),
yielding a sequence of orthonormal eigenfunctions Φx,e E (2M where À E { S [0, oc) represents the eigenvalue corresponding to the eigenfunction Φx,e, and & [mx]] indexes the multiplicity of X, denoted by m. such that Agox,e+ + xe@x,.=
for all E [l,.... m. J. Note that the basis starts with the constant function do = 1 and Ào 0.
Hence, one can write Agf = - Ei mmas delf, @x,,e)xx,e-
Lemma A.15. For any function E (2M)), such that f is decomposed into the basis foxe)==1 E. Ee (f, (AAM)) know that
= Σ
1= 1=1
for convergent summations.
Proof. By Equation (2),
IV Vo = / (Vof(z), Vof(x)) dv)l)(x)
- [x))
1=
A.5. Commutativity of Laplacian and Isometric Group Actions
Let G be a group acting isometrically on compact, smooth, boundaryless manifold M. As we stated in the main body of the paper, we have (T))) = (0)))(() for each smooth function & on manifold M, where Ty = Φ(gr).
14

---

Learning with Exact Invariances in Polynomial Time
complete proof of this claim can be found in Canzani (2013). Note that by Equation (2), this fact is equivalent to for each smooth function on manifold M.
J,a hAM = (Tg(Au(6))dvol,c)))
(3)
A.6. Weyl's Law under Invariances
Weyl's law characterizes the asymptotic distribution of the eigenvalues closed-form formula (Hörmander, 1968; Sogge, 1988; Canzani, 2013). Let us denote dimension of the space spanned by the eigenvectors corresponding to eigenvalue of the Laplace-Beltrami operator up to À as
DA Σ mx.
Theorem A.16 (Weyl's law (Hörmander, 1968; Sogge, 1988; Canzani, 2013)), Let (M,g) be compact, boundaryless d-dimensional Riemannian manifold. The asymptotic behavior of dimension count Dx, follows
Dx Wi vol(M) d/2 (1( (2
where wa +($+1)
4/2
is the volume of the unit d-dimensional ball in Rd, vol(M) is the Riemannian volume of M, and
(214-11/) represents the error term.
Define D as the dimension of the space induced by projection of the corresponding eigenspaces of Dx into the space of G-invariant functions. Tahmasebi & Jegelka (2023) proved the following characterization over this dimension as X oc.
Theorem A.17 (Dimension counting (Tahmasebi Jegelka, 2023)), Let (M. g) be a compact, boundaryless d-dimensional Riemannian manifold, and G be compact finite Lie group acting isometrically on (M. g). Then.
(Ml(M/)) xa22 + ((1(--1)/2). (2T)d
DA.
as À 2G, where again wa is the volume of the unit d-dimensional ball in Rdd
A.7. Sobolev Spaces on Manifolds
The ordinary definition of Sobolev spaces on manifolds deals with having square-integrable derivatives up to an order s. Here, since our focus is the spectral approach, present the spectral definition of Sobolev spaces.
Definition A.18 (Sobolev spaces). The Sobolev space of functions HMM) compact, smooth, boundaryless Riemannian manifold M is defined
fr.ds,(()) 11f (I = Σ D&f2 <o) H²M) = (f=
< E=
where a == 2s/d.
Note that the above definition is equivalent to the other definition of the Sobolev spaces that involves considering X instead of D above. Using Weyl's law (see Appendix A.6), one can show that both definitions are equivalent.
A.8. Sobolev Kernels
Sobolev spaces are RKHS when > d/2. Indeed, the Sobolev kernel can be defined as:
my
KH v)
D (s.s))))))
E=1
15

---

Learning with Exact Invariances in Polynomial Time
Note that any group G that acts isometrically on the manifold, also acts on the eigenspace of Laplacian via orthogonal matrices. Since orthogonal matrices preserve the inner product we conclude that
(H gu) = (M v),
for any g E G. which means that the Sobolev kernel is shift-invariant. However, this is clearly not G-invariant since produces small bump functions, which need not be invariant.
A.9. Kernel Ridge Regresion (KRR)
Consider a Desitive-Definit Symmetric (PDS) kernel K (...) on a smooth, compact, boundaryless manifold with H denoting its RKHS. The objective of Kerne Ridge Regression (KRR) estimator is to introduce the RKHS norm to the ERM objective make sure of finding smooth interpolators:
min (
JEH n Eu - vx) + =
(4)
where 17 denotes the regularization parameter that balances the bias and variance terms. Here, the objective function takes a closed-form solution to the represented theorem for kernels. This gives an efficient estimator, which is termed KRR in the literature.
However, this estimator need not be G-invariant even when trained on invariant data. To see why, note that as long as the space H includes non-invariant functions, there is a chances that we find a non-invariant function optimizing the above objective due the observation noise. Thus, the only way to make that the KRR estimator is G-invariant is to impose the assumption of having G-invariant kernels, which translated to group averaging over the Sobolev kernel:
K (H- v)
1
Σ 9EG
(oz
|G|
This method is unfortunately not computationally feasible, even though it achieves minimax optimal generalization bounds for learning under invariances with kernels (Tahmasebi & Jegelka, 2023).
B. Proofs
B.1. Minimal generating set of Group
Here, we restate and prove the following lemma on the size of the minimal generating set in group theory for completeness.
Proposition B.1. The minimal generating set S of a finite group G, has a size p(G) = |S| < ([G))
Proof. Consider the minimal generating set {g1. 92..........
? of the finite group G. For each i E (1,2....,|S1)
define G₁ (U1, . -
The identity is not equal to any of gk. and hence cannot be member of any G, since it can always be produced by combining an element with its inverse. Moreover, for all & E {1, 2, [S]}, we know that 9a-1 & G since otherwise
. 2k+ ... 9|s{) ) = G which contradicts the minimality of the generating set S for the group G. Therefore, In+1 Gn the left coset of Gn is disjoint from G,. Additionally, by definition, we know that 9 G, U., C G.+1. Hence, [G 1| Z I9n+1 Gn + |G, = 2 2. By induction, 2 = 2| 2 < |Gis]l = |G] which establishes the claim.
(91.92..... -
B.2. Constrained Optimization
In this section, we preset a detailed analysis of the constrained quadratic optimization problem that is used in Algorithm 1. Proposition B.2 (Projection into invariant subspace of eigenspaces). The optimization problem,
m
fa = arg min
(fse -
(6)
L
E=1
S.I.
E (*) = fx.
16

---

Learning with Exact Invariances in Polynomial Time
with [S| m, has closed form solution,
- -2--B BA B
where
D* (922) -
B*
(gm) - IJ
and $ denotes Moore-Penrose inverse.
Proof. For better readability, we define (g.)) = (gi)) - I, where T E IRA the identity matrix of size my, then,
B(g))
(gg))
B^
B
For ease of notation, let a = Jx E R ma and a" = ʃ2 mmm, then the optimization problem (6) can be rewritten as,
a' min 1 10 d'1 subject Bdd O.
Now, we need to show that the projection of a onto the subspace defined by {al Ba' = 0} has the following analytical form,
a" "BaaBB'(BBBBT
We form the Lagrangian,
1 / -a'l d'12 + + B'a, TBaa
L(d', where & E mR is the vector of Lagrange multipliers. By taking gradients,
OL
Oa (d' - a) + Ba 5=
thus,
a' a'=a-BA BT
(8)
Substituting back into the constraint B²aa 0,
(a (a- (a -a 0
Hence, satisfies the above linear system which may have infinite number of solutions. We claim that the choice of E* BB² )t leads the optimal solution of optimization problem 1a = |B>*² ElI Any solution & to the linear system (9), can be decomposed as g = e + Eo where to is in the nullspace of BA Hence,
(7). The objective of optimization (7) is
| <12=11 11==IIAT (5" Eb)12 BA 1 ||B
Eoll3 > ||B> T 1-
(I) follows since BA T 5* and Ba concludes the proof.
T to are orthogonal w.r.t. each other. Placing e* (B>BBTytee BBa in Equation (8)
Remark B.3 (Time complexity of optimization in each eigenspace). We arbitrarily chose the closed-form solution of the optimization problem (6) instead of iterative approaches. In the closed form solution, need to calculate the pscuedoinverse of matrix A^ Bd E SS x|Sima which can be done via singular value decomposition (SVD) in O{ The other operations are matrix multiplications that are dominated by this part in terms of computational complexity.
17

---

Learning with Exact Invariances in Polynomial Time
B.3. Main Theorem
Theorem (Learning with exact invariances in polynomial time). Consider the problem of learning with invariances with respect to finite group G using labeled dataset of size sampled from manifold of dimension d. Assume that the optimal regression function belongs the Sobolev space of functions of order i.e., f (MM)) for some d/2 and let = 2s/d. d. Then, there exists an algorithm that, given the data, produces an exactly invariant estimator f such that: runs in time O log (IG))n//(L+o) + +n(2+0) =n(2+o)((+oo))
It achieves an excess population risk (or generalization error) of of OO O((==//o+d//))
oracle calls to construct the estimator; For any x M, the estimator f(x) can be computed in time On using On oracle calls.
n(2+a)/(++a) It requires O ( ((og((()))2//10)) +
Proof. To prove Theorem we use Algorithm 1. Let start by calculating the time and oracle complexity of the algorithm.
Given dataset S of size n, first compute
FA. = Σ c()))
(10)
for each such that D2 < D= n((+)), and each l E [mx]. This requires OO O(!++//1+a)) oracle calls and can be accomplished in time O(n ((n+t)()+)))
Next, we solve the following constrained quadratic program:
TA. + arg min
(11)
fA.E
E=1
Vg
S: (* fx.
(12)
This is done for each À such that DA S /(1+a) Note that to even set up this program, we need O(S))m)) oracle calls to find the constraints. We have
(D^ = (1
(13)
for each e E [ma]. Therefore, the total oracle complexity of the proposed algorithm is
Σ
S + n (22a))((+a)
(14)
AnDaSni((44a
We have already shown in Proposition B.1 that one can use a generator set with p(G) I log( Moreover, note that
Σ
m = (n2/(1+aa)
(15)
Sn
Therefore, the oracle complexity is
o (Iog(CG)n>//0ta) (2ta)/((+a))
(16)
Let us now calculate the time complexity of finding the estimator. We have already established that compute the empirical estimation in time On ((n++/(++o)) Next, we need to solve the constrained quadratic program with log([G]) constraints and ma variables for each À such that DA S 2/(++a) Using the proposed algorithm in Appendix B.2 and also Remark B.3, we can solve each of these constrained quadratic programs in time Olog" ([G))))) Therefore, the total time complexity of this step is bounded by
o (
log (1G))3 SxD05
Σ
- (1og)((G))))
(17)
18

---

Learning with Exact Invariances in Polynomial Time
This proves that the total time complexity of Algorithm is
o ( (Gl)) (n =
(18)
Finally, note that given F. one can evaluate it on new unlabeled data x E M using the formula:
ma
f(x)=
E E Fredse(E).
(19)
with D = nn1((aa) which requires both time and oracle complexity of O(n)/(2+a)).
To complete the proof, we need to study the convergence of the population risk of the proposed estimator. We first note that
R(f) Bllff f (l(aamm) 2 f ( 2Eillf (()
(20)
where p denotes the orthogonal projection of the function f* onto the space of eigenfunctions with eigenvalues satisfying D> & D. Moreover, f D
First, let us upper bound the second term. Note that, according to the assumption, S E (M). Thus,
ma
Σ
Σ (fx.)²
(21)
Dr
my
Σ
Σ
D (S2))
(22)
i=D
D EDRSS D2(S)))
(23)
DD
DR(F
(24)
E
D |1 PFFMMM)
(25)
Now we focus on the first term. Note that
E - f20l = Σ
E E fx.e
(26)
DD t=1l
According to the definition, we have
12 - (x==),)((+)ono())) = En Luolvoox (x)),
(27)
for each X, l. Moreover, Jx is the empirical estimation obtained from data:
FA. 1 a n2
Σ (x.))
(28)
Thus, obtain
BlJ
5x
E [VVAA(() E(udx,
(29)
n
1
E
((( + BLJ
(30)
1
+ -BT000/0--01LL000000000000000000
(31)
1
<
(0²
(32)
n
1
(0² + || (l)())
(33)
19

---

Learning with Exact Invariances in Polynomial Time
where we used the orthonormality of the eigenfunctions Φx,e- Then, summing this up to dimension D gives:
D (o² -1f"
Bill f'gol - 72
(34)
Note that, by definition, - where Pc (2) + (x) is the orthogonal projection operator onto the invariant functions. Therefore, we have
B11l - 13plliu = B[| 12D (
(35)
= =F[] - Pat
(36)
(37)
D (o2 + 11 -1
(38)
where the penultimate step follows from PafeD feD Therefore, we can combine the two terms to derive the following population risk bound:
D R() - 11) S n (o² + +11Ml))))) +
(39)
We can now specify the above bound to D = n (((too)) which is used in the algorithm, to get:
R(F) = El1 - fr 1"122())) s n -a/(ta)) (o² + 115 (l== + - If ('
(40)
which is equivalent to
R(F) O(n ((n-0(((to))) -a((1+))).
(41)
This completes the proof.
Remark B.4. Note that other choices of D may or may not yield better bounds depending the sparsity of the solution. For this sparsity-unawar upper bound that we use, such a choice of D is optimal. Additionally, since we focus on polynomial time algorithms, we cannot choose exponentially large D even if they deliver gains in sample complexity.
C. Experimental Results
The plots for the experiments discussed in Section 6 are presented below.
20

---

Learning with Exact Invariances in Polynomial Time
Discrepancy Values Number of Training Samples
Number Samples
KRR-A-50
KNR-A-100
KRR-A=150
10-1
KRR-A=200
Discrepancy Values (Log Scale)
200
400
600
800
1000
Number of Training Samples (Niaa)
Figure 1. Invariance Discrepancy measure of Keree Ridge Regression (KRR) for various choices of the regularization parameter A. The resulting estimator, KRR, not invariant with respect
group of sign averages {=1}", whereas Spec-Avg G-invariant by construction. Each point in the plot represents average over 10 different random seeds. The Invariance Discrepancy measure used for this plot defined as sup.exx.cc [xx) f(g=),, where f the estimator. The set X' consists points uniformly sampled from interval [-1, 1)3, independently identically distributed.
Test Errors vs. Number of Training Samples
Method
KRR-1-50
KRR-A-100
KRR-A=200
Spec-AVG (Ours)-D-176
(Ours)-D-56
Text Enror (Log Scale)
100
Spec-AV6 (Ours)-D-11
Spec AVG (Ours) D-1
10-1
10a
10a
10a
Number of Training Samples (Nowa)
Figure Test error (empirical excess population risk) of KRR for different choices of the regularization parameter À and Spec-Avg for different choices of the sparsity parameter D. Conceptually, higher values of À and lower values of D encourage sparser representations for the estimators XRR and Spec-Avg, respectively. suggested by our theory, can observed that test error rates of same order can be achieved by Spec-Avg and KRR with appropriate choices of hyperparameters. Note that the test errors are shown on log scale. Their almost linear behavior implies that they are polynomial functions the number training samples with comparable orders. note that each point in the plot represents average over 10 different random seeds.
21


Reviews:
[{"review_id": "NHN2lwbBh5", "reviewer": "Reviewer_jn5T", "summary": "This work addresses the problem of learning exactly invariant models in the kernel regression setting. Given an assumption on the smoothness of the target function, they propose an algorithm for computing an invariant estimator in polynomial time with respect to the number of samples and polylogarithmic with respect to the cardinality of the group, which is significantly more efficient than other common techniques in invariant learning such as frame averaging and data augmentations. Specifically, the authors reformulate the problem as an optimization in the spectral domain and showcase how they can reduce it into an equivalent problem of optimizing a finite number of linear constrained quadratic programs. While the main text focuses on an extensive derivation of the proposed algorithms, the authors also describe the application of the algorithm in some simple examples, which facilitate the understanding of the method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your positive and constructive feedbacks. \n\n> 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.\n\n\n**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.\n\n\n\n> 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.\n\n\n**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!", "claims_and_evidence": "All of the claims of the paper, mainly theoretical, are supported by comprehensive proofs.", "methods_and_evaluation_criteria": "While the evaluation of the proposed method is limited to a simple problem, it is sufficient to showcase some quantitative differences between the proposed algorithm and the non-invariant Kernel Ridge Regression (KRR) that acts as a baseline.", "theoretical_claims": "I reviewed the theoretical derivation in the main text and the supplementary material. I didn't detect any issues.", "experimental_designs_or_analyses": "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.", "relation_to_broader_scientific_literature": "This work contributes to the field of invariant machine learning and, specifically, invariant kernel regression. As stated in the introduction and related work, there is a large literature on invariant kernel regression that can suffer from higher computational complexity, especially in the case of larger symmetry groups. In this context, the authors' contribution is the introduction of a polynomial algorithm for performing kernel regression that respects known invariances.", "essential_references_not_discussed": "I didn't find any significant works that were not referred to in the paper.", "other_strengths_and_weaknesses": "Strengths:\n- A major strength of the proposed algorithm is that while it achieves polynomial time complexity, it doesn't sacrifice the generalization error, achieving the same performance as non-invariant learning methods.\n- The authors provide a comprehensive presentation of the theoretical tools that they then utilize to analyze the proposed algorithm's computational complexity and generalization performance.\n\nWeaknesses:\n- 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. \n- Similarly, the limitation of the proposed algorithm in kernel regression, while allowing for extensive theoretical analysis, can limit the application of the proposed method.", "other_comments_or_suggestions": "No other comments or suggestions", "questions_for_authors": "I don't have any significant questions for changing the paper's evaluation.", "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": "Vf65sXtYNg", "reviewer": "Reviewer_TTY3", "summary": "This paper investigates the statistical-computational trade-offs involved in learning with invariances, particularly in the context of kernel regression. While the Kernel Ridge Regression (KRR) estimator can be applied to this problem, it lacks invariance unless combined with group averaging, which is computationally expensive for large groups. This raises the question of whether statistically sound estimators with efficient time complexity can be developed. The authors demonstrate that by reformulating the problem and reducing the number of constraints using group laws, the task can be expressed as solving an infinite series of quadratic optimization programs subject to linear constraints. The paper present a polynomial-time algorithm that achieves an exactly invariant estimator.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n> 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.\n\n\n\n**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. \n\n\n> 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?\n\n\n\n**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.\n\nRegarding 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.", "claims_and_evidence": "The claims made in the submission appear to be supported by a rigorous theoretical framework", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria appear to be well-suited for the problem and application at hand.", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "It seems well-founded.", "relation_to_broader_scientific_literature": "Kernel methods, including Kernel Ridge Regression (KRR), are well-established in machine learning for their ability to model nonlinear relationships. However, standard KRR does not inherently handle invariances. The paper leverages the theoretical foundations of KRR but reformulates the problem to incorporate invariances directly.", "essential_references_not_discussed": "null", "other_strengths_and_weaknesses": "Strengths:\nThe paper is clearly written and accessible, making it easy to follow. It introduces a novel algorithm with two key strengths: computational efficiency and the ability to enforce group invariances. The theoretical analysis appears thorough and well-developed, providing a solid foundation for the proposed method.\n\nWeaknesses:\nConducting 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.", "other_comments_or_suggestions": "null", "questions_for_authors": "Could the analysis of the main theorem be extended to cases where the regression function does not belong to the hypothesis space?\nCould 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?", "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": "Mp1Xj9I3Tm", "reviewer": "Reviewer_pzD8", "summary": "The paper suggested that, in Kernel Ridge Regression (KRR) under certain assumptions including the kernel space, achieving exact invariance of the kernel function through group averaging is feasible in polynomial time. This is done by using a finite number of bases derived from the constrained spectral method for Laplace-Beltrami operators and leveraging the fact that a small number of generators can represent a large number of group elements.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n> the paper should empirically compare .... the invariance error of the trained model to ordinary kernels even if the results seem obvious.\n\nThe 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.\n\nPlots 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.\n\n\n> ... empirically compare actual running times even if the results seem obvious ... at least one real dataset, such as from the UCI repository ...\n\nThanks 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.\n\n> ... If a large number of bases is necessary in real cases, this method might not be beneficial ...\n\nThanks 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.\n\nIt 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.\n\nIn 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.\n\n> ... approximating group averaging by randomly sampling group elements ...\n\nThe 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.\n\n> The notations $D^\\lambda$ and $D_{\\lambda}$ are pretty confusing.\n\nThank 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.\n\n\n[1] https://medium.com/%40ceo_44783/why-i-prefer-gpt-4-over-gpt-4o-cf504741e156", "claims_and_evidence": "The claim presented as Theorem 1 is theoretically convincing. However, empirically there is limited evidence to confirm its efficiency.", "methods_and_evaluation_criteria": "Using a limited number of eigenfunctions and group elements is reasonable. We can choose the target operator based on prior knowledge of the data. It allows the kernel space derived from the operator to span all group elements using only the group's generators.", "theoretical_claims": "I did not check the proofs explicitly, but overall I got an intuition about why achieving polynomial time is feasible.", "experimental_designs_or_analyses": "The synthetic data experiments with sign-invariances on the torus manifold support the efficiency of training regarding the number of training samples. However, since the main theorem and the paper's title emphasize learning with invariances in polynomial time, the paper should empirically compare actual running times (e.g., wall-clock times) and the invariance error of the trained model to ordinary kernels, even if the results seem obvious. Additionally, at least one real dataset, such as from the UCI repository, should be included to show how many bases (D) are needed in practical scenarios to achieve reasonable performance and to show performance with larger groups like finite rotation groups. If a large number of bases is necessary in real cases, this method might not be beneficial compared to approximating group averaging by randomly sampling group elements, despite losing exact invariance.", "relation_to_broader_scientific_literature": "Limitation of prior group averaging could be partially resolved by this paper in KRR, although its efficiency in real datasets remains uncertain.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Although the theoretical guarantees are strong and the method is pretty insightful, as I mentioned in the experimental design or analyses section, empirical evidence is limited to support the efficiency in other datasets or groups.", "other_comments_or_suggestions": "The notations $D_\\lambda$ and $D^\\lambda$ are pretty confusing.", "questions_for_authors": "None", "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": "SzkbBVl2tq", "reviewer": "Reviewer_nZmY", "summary": "The paper addresses the challenge of learning with exact invariances (symmetries) in kernel regression. Traditional methods either fail to provide polynomial-time solutions or are not applicable in the kernel setting. The authors propose a polynomial-time algorithm that achieves exact invariances using oracle access to the geometric properties of the input space. The algorithm achieves the same excess population risk as the original kernel regression problem, making it the first polynomial-time algorithm to achieve exact invariances in this context.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for acknowledging the merits of our work and for raising interesting questions.\n\n\n> The algorithm relies on oracle access to the geometric properties of the input space, which may not always be available in practical applications.\n\n\n**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.\n  \n\n> In Algorithm 1, we don't know alpha in practice. How does this affect the efficiency of the proposed algorithm? \n\n\n**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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proof appears to be correct, although I haven't verified it line by line.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "The paper's key contributions advance several important areas of prior research, including learning with invariances, kernel methods, and optimization. By addressing the limitations of traditional methods and providing a polynomial-time algorithm for learning with exact invariances, the paper makes a significant theoretical and practical contribution to the field.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1.The paper provides a rigorous theoretical framework for learning with exact invariances, supported by tools from differential geometry and spectral theory.\n\n2. The proposed algorithm runs in polynomial time, making it practical for real-world applications where traditional methods are computationally prohibitive.\n\n3. The algorithm achieves the same generalization error as kernel regression without invariances, showing that exact invariances do not compromise statistical performance.\n\nWeaknesses:\n1. The algorithm relies on oracle access to the geometric properties of the input space, which may not always be available in practical applications.\n\n2. The paper lacks extensive experimental validation, but the theoretical contribution is solid.", "other_comments_or_suggestions": "No", "questions_for_authors": "In Algorithm 1, we don't know $\\alpha$ in practice. How does this affect the efficiency of the proposed algorithm?", "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": "ORWx8scAPa", "reviewer": "Reviewer_GpVg", "summary": "Building from results on Riemannian manifolds, group theory, and the spectral properties of the Laplace-Beltrami operator, the authors propose a learning algorithm to minimize the population risk in the class of Sobolev space (s times differentiable for s >= 2d where d is the dimension of the input space, here a Riemannian manifold) under the constraint that the returned estimator achieves *exact invariance* with respect to a (provided) group of transformations acting on the input space. Thanks to a nice observation on group invariance presented on page 5 (just before Definition 5.1) and from the fact that the size of the group generator is bounded by the logarithm of the group size, the algorithm scales only logarithmically with the group size and polynomially with all other relevant parameters such as d and the number n of training examples. Moreover, the authors argue that the Sobolev regression function can be approximated well by a superposition of at most D eigenvectors (of the Laplace-Beltrami operator) for some reasonable D. As a consequence, the authors **seem** to claim that their algorithm \"learns\" (in polynomial time) a good approximation of the Sobolev regressor which achieves exact invariance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition of our work’s merits and their valuable comments.\n\n> 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.\n\n**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).\n\n\n\n\n\n\n\n\n> 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.\n\n\n**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.\n\n\n> 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.\n\n\n**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.\n\n\n> The book of Sholkopf ans Smola was published by MIT Press in 2002, not 2018. \n\n\n**Answer:** Thanks for pointing this out! We will correct it in our next version!\n\n\n>  There are a few conflicting notations. In the supplementary material, g is used to represent a group element and the metric tensor!\n\n\n**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.\n\n\n> \\eta is the regularizer of the KRR of Equation 8. But that regularizer is referred to as \\lambda on page 8.\n\n**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.\n\n\n> 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?\n\n**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.\n\n\n[1] Bach, Francis. Learning theory from first principles. MIT press, 2024", "claims_and_evidence": "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). \n\nIs 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.", "methods_and_evaluation_criteria": "This is a theoretical paper and the presented theory is nice an relevant; but very complicated to understand for those like me who have very little background on Riemannian geometry. Why do we need to treat the input space as a compact boudaryless Riemannian manifold? Why not just a compact subset of R^d ? This would make your paper more accessible to the ICML audience. Do you need to consider the input space X as a Riemannian manifold because of the group action on X? I think the authors should provide the motivation for considering Riemannian minifolds.", "theoretical_claims": "I was able to verify the claim on \"reducing the number of constraint\" on page 5 and the property proven in appendix C1. I was able to follow sections 3, 4, and 5 but it took me quite a while... However, many of the definitions, lemmas and theorems in the appendix are just to advanced for me. I would need much more time to understand them.", "experimental_designs_or_analyses": "The small experiment seems OK and supports the theoretical claims and results.", "relation_to_broader_scientific_literature": "The paper nicely position itself in the literature on learning under invariance.", "essential_references_not_discussed": "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.\n\nOtherwise, I have not identified any other missing references.", "other_strengths_and_weaknesses": "The book of Sholkopf ans Smola was published by MIT Press in 2002, not 2018.", "other_comments_or_suggestions": "There are a few conflicting notations. In the supplementary material, g is used to represent a group element and the metric tensor! \n\n\\eta is the regularizer of the KRR of Equation 8. But that regularizer is referred to as \\lambda on page 8.", "questions_for_authors": "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?", "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:

Meta-review: This submission is centered around machine learning with (exact) invariances. Particularly, the authors show (Theorem 1) that it is possible to learn a G-invariant estimator (G being a finite group) in polynomial time w.r.t. the dimension (of the smooth manifold forming the domain of the true Sobolev regression function), the sample size, and log(|G|) [where |G| denotes the cardinality of the minimum generating set of G which can be even/significantly smaller than the cardinality of G], achieving the same excess risk guarantee as kernel ridge regression (KRR; which might not satisfy the invariance constraints). The approach provides an alternative to existing methods like data augmentation and group averaging with an exponential improved dependence on |G|. A numerical example is given to illustrate the applicability of the construction, providing a comparison with KRR.

Kernel methods are at the forefront of principled data science; similarly, learning with invariances is a key question of the area. The authors propose a novel method at the intersection of these domains in a clearly-written manuscript which can be of definite interest to the ICML community from both theoretical and practical perspective.
Decision: Accept (spotlight poster)