The Exact Sample Complexity Gain from Invariances for Kernel Regression
Authors: Behrooz Tahmasebi
Stefanie Jegelka
Venue: NeurIPS 2023 spotlight (2023)
Keywords: invariances
manifolds
sample complexity
TL;DR: We prove minimax optimal rates for kernel ridge regression with group invariances on manifolds.

Abstract: In practice, encoding invariances into models improves sample complexity. In this work, we study this phenomenon from a theoretical perspective. In particular, we provide minimax optimal rates for kernel ridge regression on compact manifolds, with a target function that is invariant to a group action on the manifold. Our results hold for any smooth compact Lie group action, even groups of positive dimension. For a finite group, the gain effectively multiplies the number of samples by the group size. For groups of positive dimension, the gain is observed by a reduction in the manifold's dimension, in addition to a factor proportional to the volume of the quotient space. Our proof takes the viewpoint of differential geometry, in contrast to the more common strategy of using invariant polynomials. This new geometric viewpoint on learning with invariances may be of independent interest.

The Exact Sample Complexity Gain from Invariances for Kernel Regression
Behrooz Tahmasebi MIT CSAIL bzt@mit. edu
Stefanie Jegelka MIT CSAIL and TU Munich stefje@mit.. edu
Abstract
In practice, encoding invariances into models improves sample complexity. In this work, we study this phenomenon from theoretical perspective. In particular, we provide minimax optimal rates for kernel ridge regression on compact manifolds, with a target function that is invariant to group action on the manifold. Our results hold for any smooth compact Lie group action, even groups of positive dimension. For a finite group, the gain effectively multiplies the number of samples by the group size. For groups of positive dimension, the gain is observed by reduction in the manifold's dimension, in addition to a factor proportional to the volume of the quotient space. Our proof takes the viewpoint of differential geometry, in contrast to the more common strategy of using invariant polynomials. This new geometric viewpoint on learning with invariances may be of independent interest.
1 Introduction
In broad range of applications, including machine learning for physics, molecular biology, point clouds, and social networks, the underlying learning problems are invariant with respect to a group action. The invariances
observed widely in practice, for instance, in the study of high energy particle physics [21, 32]. galaxies [23, 15, 2], and also molecular datasets [1. 59, 36] (see [67] for survey). In learning with invariances, problem's invariance structure as much as possible. An essential question is thus: what are the fundamental benefits of model invariance, e.g., in terms of sample complexity?
aims to develop powerful architectures that exploit the
Several architectures for learning with invariances have been proposed for various types data and invariances, including DeepSet [70] for sets, Convolutional Neural Networks (CNNs) [28], PointNet [53, 54] for point clouds with permutation invariance, tensor field neural networks [62] for point clouds with rotations, translations, and permutations symmetries, Graph Neural Networks (GNNs) [58], and SignNet and BasisNet [37] for spectral data. Other works study invariance with respect to the orthogonal group [63], and invariant and equivariant GNNs [42]. These architectures are to exploit the invariance of data as much as possible, and are invariant/cquivaaiant by design.
In fixed dimensions, one common feature of many invariant models, including those discussed above, that the data lie on a compact manifold (not necessarily a sphere, e.g., the Stiefel manifold for group action on that manifold. Thus, characterizing
spectral data), and are invariant with respect the theoretical gain invariances corresponds to studying the gain of learning under group actions on manifolds. Adopting this view, in this paper, we answer the question: how much gain in sample complexity is achievable by encoding invariances? As this problem algorithm and model dependent, it is hard to address in general. A focused version of the problem, but still interesting, is to study this sample complexity gain in kernel-based algorithms, which is what we address here. As neural networks in certain regimes behave like kernels (for example, the Neural Tangent Kernel (NTK) [26, 34)), the results on kernels should be understood as relevant to a range of models.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Formally, we consider the Kernel Ridge Regression (KRR) problem with i..dd data on compact manifold M. The target function lies in a Reproducing Kernel Hilbert space (RKHS) of Sobolev functions H (M), 2 O. In addition, the target function is invariant to the action of an arbitrary Lie group on the manifold. We aim to quantify: by varying the group G. how does the sample complexity change, and what is the precise gain as G grows?
Main results. Our main results characterize minimax optimal rates for the convergence of the (excess) population risk (generalization error) of KRR with invariances. More precisely, for the Sobolev kemel, the most commonly studied case of kernel regression, we prove that a (excess) population risk
o² vol(M//G s/(s+d/2) is both achievable and minimax optimal, where o²
(generalization error)
is the variance of the observation noise, vol(M//) is the volume' of the corresponding quotient space, and d is the effective dimension of the quotient space (see Section 4 for a precise definition). This result shows a reduction in sample complexity in two intuitive ways: (I) scaling the effective number of samples, and (2) reducing dimension and hence exponent. First, for finite groups, the factor vol(M/G) reduces to vol( GG., and can hence be interpreted as scaling the effective number of samples by the size of the group. That is, each data point conveys the information of | data points due the invariance. Second, and importantly, the parameter dl in the exponent can generally be much smaller than dim(M), which would be the correspondent of d in the non-invariant case. In the best case, d diM ddim(G), where dim (G) is the dimension of the Lie group G. Hence, the second gain shows a gain in the dimensionality of the space, and hence in the exponent.
Our results generalize and greatly expand previous results by Bietti et al. [5], which only apply to finite groups and isometric actions and are valid only on spheres. In contrast, we derive optimal rates for all compact manifolds and smooth compact Lie group actions (not necessarily isometric), including groups of positive dimension. In particular, the reduction in dimension applies to infinite groups, since for finite groups dim(G) reduction in sample complexity that was not possible with previous assumptions. Our rates are consistent with the classical results for learning in Sobolev spaces on manifolds without invariances [24]. To illustrate our general results, in Section 5, we make them explicit for kernel counterparts of popular invariant models, such as DeepSets, GNNs, PointNet, and SignNet.
O. Hence, our results reveal a new perspective the
Even though our theoretical results look intuitively reasonable, the proof is challenging, We study the space of invariant functions as a function space on the quotient space M//G. To bound its complexity, we develop a dimension counting theorem for functions on the quotient space, which is at the heart of our analysis and of independent interest. The difficulty is that MM/G is not always manifold. Moreover, it may exhibit non-trivias boundaries that require boundary conditions to study function spaces. Different boundary conditions can lead to very different function spaces, and priori the appropriate choice for the invariant functions is unclear. We prove that smooth invariant functions on M satisfy the Neumann boundary condition on the (potential) boundaries of the quotient space, thus characterizing exactly the space of invariant functions.
The ideas behind the proof are of potential independent interest: we provide differential geometric viewpoint of the class of functions defined on manifolds and study group actions on manifolds from this perspective. This stands in contrast to the classical strategy of using polynomials generating the class of functions [46, 5), which is restricted to spheres. To the best of our knowledge, the tools used in this paper are new to the literature on learning with invariances.
In short, in this paper we make the following contributions:
We characterize the exact sample complexity gain from invariances for kernel regression on compact manifolds for arbitrary Lie group action. Our results reveal two ways to reduce sample complexity, including a new reduction in dimensionality that was not obtainable with assumptions in prior work.
Our proof analyzes invariant functions function space on the quotient space; this differential geometric perspective and our new dimension counting theorem, which is at the heart of our analysis, may be of independent interest.
'The quotient space is not manifold, but one still define notion of volume for it; see Section 4.
2

---

2 Related Work
The perhaps closest related work to this paper is [5], which considers the same setup for finite isometric actions on spheres. We generalize their result in several aspects: the group actions are not necessarily finite or isometric, and the compact manifold is arbitrary (including compact submanifolds of IR'),, allowing to observe a new axis of complexity gain. Mei et al. [46] consider invariances for random features and kernels, but in a different scaling/regime; thus, theirs are not comparable to our results. For density estimation on manifolds, optimal rates are given in [24], which are consistent with our theory. McRae al. [45] show non-asymptotic sample complexity bounds for regression on manifolds. A similar technique was recently applied in [40]. but for very different setting of covariate shifts.
The generalization benefits for invariant classifiers are observed in the most basic setup in [61], and for linear invariat/equivariint networks in [20. 19]. Some works propose covering ideas to measure the generalization benefit of invariant models [71], while others use properties of the quotient space [57, 50]. It is known that structured data exhibit certain gains for localized classifiers
[14]. Sample complexity gains are also observed for CNN on images [17, 35]. Wang et al. [66] incorporate more symmetry in CNNs improve generalization.
Many works introduce models for learning with invariances for various data types; in addition to those mentioned in the introduction, there are, c.g., group invariant scattering models [41, 9]. A probabilistic viewpoint of invariant functions [6] and a functional perspective [72] also exist in the literature. The connection between group invariances and data augmentation is addressed in [13, 39].
Universal expressiveness has been studied for settings like rotation equivariant point clouds [18], sets with symmetric elements [44], permutation invariant/equivarian functions [56], invariant neural networks [55, 69, 43], and graph neural networks [68, 49]. Lawrence et al. [30] study the implicit bias of linear equivariant networks. For surveys invariant/equivariant neural networks, see [22, 8).
3 Preliminaries and Problem Statement
Consider smooth connected compact boundaryless (M))MMMmmdiiiinaa (Riemannian) manifold (M,g). where g is the Riemannian metric. Let G denote an arbitrary compact Lie group of dimension dim(G) (i.e. a group with smooth manifold structure), and assume that G acts smoothly on the manifold (M, g); this means that each т E G corresponds to a diffeomorphism t : .M -> M, i.e., a smooth bijection. Without loss of generality,
can assume that G acts isometrically on (M, (M,g), i.e., G a Lie subgroup of the isometry group ISO(M,g) g). To see why this is not restrictive, given a base metric g, consider new metrie ğ = pc g), where Ja is the left-invariant Haar (uniform) measure of G. and r'g is the pullback of the metric g by Under the new metric, G acts isometrically on (M,g). g). We review basic facts about manifolds and their isometry groups in Appendix A. and Appendix A.2.
We are given a dataset S = {11,, v.) i 1,2...., S (M R)" of n labeled samples, where I; "ia 14, for the uniform (Borel) probability measure dy((z)= == vol(M]] d vz) Here, d vol (x) denotes the volume element of the manifold defined using the Riemannian metric g. We assume the uniform sampling for simplicity; our results hold for non non-uniform cases, too. The hypothesis class is set F C (M,, G) C (2M)) including only G-invariant square-integrable functions on the manifold, i.c. those there exists function S' E F such that y, = f(xaa) + for each (I,, JK) E S. where e, are conditionally zero-mean random variables with variance a², i.e., [[G[a]] = and [B[?]o:]] < a².
(2M satisfying f(r(z)) f(z) for all G. We assume that
Let K= MM* x M denote a continuous positive-definite symmetric (PDS) kernel on the manifold M, and let H C (MM denote its Reproducing Kernel Hilbert Space (RKHS). The kernel K is called
2 Although the results in this paper can be easily extended to manifolds with boundaries, for simplicity, we focus on the boundaryless case.
3

---

G-imvariant if and only if for all r, y E M,
( v) = K
(I)
for any T. E G. In other words, (xx, = K([x), [u]), where [=] = [r(x) : E G} is the orbit of the group action that includes x.
The Kernel Ridge Regression (KRR) problem on the data with a G-invariant kernel asks for the function f that minimizes
2 Σ
f== arg min {R(F) JEH
72 yo f(x:))) + m
(2)
By the representer theorem [48], the optimal solution / E H is of the form f = a.K (a:,)) for a weight vector a E IR". The objective function R(f) can thus be written as
R(F) f Kală naa" Ka, Ka,
where y (y), ..., 3n)) and K (,n,,, is the Gram matrix. This gives the closed form solution (K + mnI) Using the population risk R(f) = Ezsally fx))) the effective ridge regression estimator is defined as
fen == arg JEH
arg.inn min {RU)+mIl/I) n
(4)
This paper focuses on the RKHS of Sobolev functions, H = = (M) = H* L (M, (M, O. This includes all functions having square-integrable derivatives up to order Note that (M) includes only continuous functions when & > dim(MM)22. Moreover, it contains only continuously differentiable functions up order l when dim(M)/2 + & (Appendix A.10). Note that (M) an RKHS and only s > dim(M)/2.
4
Main Results
Our first theorem provides an upper bound on the excess population risk, or the generalization error, of KRR with invariances.
Theorem 4.1 (Convergence rate of KRR with invariances). Consider KRR with invariances with respect to a Lie group G on the Sobolev space Him s > d/2, with di/(M/ Assume that f e Hall (M) for some 0 E (0, 11, and let = (n + for a positive k. Then,
Wa o² vol(M/GG) 0e/(0s+d/2)
E R(( -R())
32 KD (2
||
d/(9o-d/2) 7e00 (M)
(5)
with the optimal regularization parameter
1
Wd o² vol(M/G) 0s/(Ostd/2)
17
2x00 1+1
Hen (M) (2T)d
(6)
n
where wa is the volume of the unit bull in Rdd.
Theorem 4.1 allows to estimate the gain in sample complexity from making the hypothesis class invariant. Setting G {ido (i.e., the trivial group) recovers the standard generalization bound without group invariances. In particular, without invariances, the dimension d becomes dim(M). and the volume vol(M//) becomes vol(M). Hence, group invariance can lead a two-fold gain:
Exponent: the dimension d in the exponent can be much smaller than the corresponding dim(M).
'This definition is stronger from being shift-invariant: kernel K is shift-invariant (with respect to the group G) if and only if K(2, x) ((T(z))(())) for all a, y M, and all For any given shift-invariant kernel K. one can construct its corresponding G-invariant kerel K (z, y) = fo K ((((x), ())po(T)) where pe is the left- intariaati Haar (uniform) measure of G.

---

Effective number of samples: the number of samples is multiplied by
Wiim(M)) (27))
vol(M)
wa/ (2x)
(MI(M/G)
The quantity (7) reduces to |G] G is a finite group that efficiently acts on M (i.e., if any group element acts non-trivially on the manifold). Intuitively, any sample conveys the information of G data points, which can be interpreted as having effectively n x [G] samples (compared to non-invariant KRR with samples). For groups of positive dimension, it measures how the group is contracting
the volume of the manifold. Note that for finite groups, one always has vol.M. vo/[ 2
Dimension and volume for quotient spaces. Theorem 4.1, the quotient space M/G is defined as the set of all orbits [xr] == {r(ar) r E G). x E M, but M/G is not always (boundaryless) manifold (Appendix A.5 and A.6). Thus, is not immediately possible to define its dimension and volume. The quotient space is finite disjoint union of manifolds, each with its specific dimension/volume In Appendix A.5 and A.6, we review the theory of quotients of manifolds, and observe that there exists an open dense subset Mo M such that Ma/G is open and dense in M/G., and more importantly, it is a connected precompact manifold. Ma/ G is called the principal part of the quotient space. has the largest dimension among all the manifolds that make up the quotient space.
The projection map т : -Mo - Mo/G G induces a metric on Ma/G and this allows us to define vol(M/G) vol vol(Mo/G Note that vol(M//)) depends on the Riemannian metric, which itself might depend on the group G if we start from a base metric and then deform make the action isometrie. The volume vol(Mo// is computed with respect to the dimension of Ma/ G, thus being nonzero even dim(Mo/G) < dim(M).
The effective dimension of the quotient space is defined as d == dim(Ma//)), Alternatively, one can define the effective dimension as
d := dim(M) dim(G) + min dim(G,),
(8)
zEM
where G := (T G r(x) æ} is called the isotropic group of the action at point E M. For example, if there exists a point x E M with the trivial isotropy group G2 = {idg]. then d = dim(M)- dim(G).
Remark 4.2. The invariant Sobolev space satisfies (M) S Hill S (M). If the regression function f* does not belong to the Sobolev space MinnnMM (i.e.. A (0, 1)), the achieved exponent only depends on Os (i.e., the smoothness of the regression function I and not the smooth- ness of the kernel). The bound decreases monotonically increases: smoother functions easier to learn.
The next theorem states our minimax optimality result. For simplicity, we assume 0 = 1.
Theorem 4.3 (Minimax optimality). For any estimator f.
Wa o² vol(MMG) s/(s+d/2) (2TTd (2T)d
E [(((F) (R()) 2 Cx
sup I E'EH (M)
n
1 Ifll (M))
where Cj is constant only depending on k, and wa is the volume of the unit ball in Rdd
An explicit formula for C₂ is given in the appendix. Note that the above minimax lower bound not only proves that the achieved bound by the KRR estimator optimal, but also shows the optimality of the prefactor characterized in Theorem 4.1 with respect to the effective dimension d (up to multiplicative constants depending on K).
4.1 Proof Idea and Dimension Counting Bounds
To prove Theorem 4.1, we develop general formula for the Fourier series of invariant functions
manifold. particular, we argue that a smooth G-invariant function f: .M- + IR corresponds to
smooth function f M/G -> on the quotient space M/G, where f((x)) = f(x:) for all E M.
Hence, we view the space of invariant functions as smooth functions on the quotient space.
5

---

The generalization bound essentially depends on a notion of dimension or complexity for this space, which allows bounding the bias and variance terms. We obtain this by controlling the eigenvalues of the Laplace-Beltrami Beltrami operator, which is specifically suitable for Sobolev kernels.
The suplace-Beltrane operator Ag is the generalization of the usual definition of the Laplacian operator the Euclidean space R to any smooth manifold. It can be diagonalized in L (M) [12]. In particular, there exists an orthonormal basis { of L (M) starting from the constant function do = 1 such that 6 + Xecre 0, for the discrete spectrum O A À S A2 S .... Let call {d)(x)) the Laplace-Beltrami Beltrami basis for (MM. Our notion of dimension of the function space is (()) == #(e: d S A}. It can be shown that a Lie group G acts smoothly on the compact manifold M, then G also acts on eigenspaces of the Laplace-Beltraml operator. Accordingly, we define the dimension [Q;; G) as the dimension of projecting the eigenspaces of the saplace-Beltramt operator on M onto the space of G-invariant functions, that is, the number of invariant eigenfunctions with eigenvalue up to À (Appendix A.7).
Characterizing the asymptotic behavior of [(;; G) is essential for proving our main results on the gain of invariances. Intuitively, the quantity N (A; G) corresponds to the fraction of functions that are G-invariant. One of this paper's s main contributions is to determine the exact asymptotic behavior of this quantity for the analysis of KRR. The tight bound on (A;; G) can be of potential independent interest other problems related to learning with invariances.
Theorem 4.4 (Dimension counting theorem). Let (M,g) be a smooth connected compact boundary- less Riemannian manifold of dimension dim(M) and let G be a compact Lie group of dimension dim G) acting isometrically on (M,9). Recall the definition of the effective dimension of the quotient space == dim(M) - (G) + minzeM (Gm. Then,
Wa (2x)d vol,M//)x*++ +
G)
(10)
as x - 0c, where wa is the volume of the unit ball in Rd
In Appendix B, we prove generalized version of the above bound (i.e., local version).
To see how this counting bound relates to Sobolev spaces, note that by Mercer's theorem, a positive- definite symmetric (PDS) kernel K : M - R can be diagonalized in an appropriate orthonormal basis of functions in (MM). Indeed, the kernel of the Sobolev space (MM - (²M is Laplace-Beltrami
diagonalizable in the Laplace- Beltrami basis*:
(H,())(Z = Σ min(1, N7 "))((()())))
(11)
where Φz, l = 0, 1...., form a basis for (MM such that مه0r + A 0 for each f. For the G-invariant RKHS (MM), the sum restricted to G-invariant eigenfunctions (Appendix A.9). is evident that Theorem 4.4 provides an important tool for analyzing the Sobolev kernel development with respect to the eigenfunctions of Laplacian.
4.2 Proof Idea of the Dimension Counting Theorem
For Riemannian manifolds, Weyl's law (Appendix A.4) determines the asymptotic distribution of eigenvalues. The bound in Theorem 4.4 indeed corresponds Weyl's law, if we write it in terms of the quotient space M/G. But, in general, Weyl's law does not apply to the quotient space M/G. So this intuition is not rigorous. First, the quotient space is not always a manifold (Appendix A.5). Second, even if we restrict our attention to the principal part Mo/ G discussed above, which is provably a manifold, other complications arise.
In particular, the quotient Mo/G can exhibit a boundary, even if the original space is boundaryless. For concrete example, consider the circle S1 = { v) x² + 3² 1). parameterized by the angle 0 E [0, 2T), under the isometric action G = {idg: J.. where 7 (0) the y-axis. The resulting space is semicircle with two boundary points (0, +1).
0 is the reflection across
Many kernels in practice satisfy this condition, e.g., any dot dot-product kernel on sphere. While we present the results of this paper for Sobolev kernels, one can use any kemel satisfying the condition in Proposition A.9 and apply the same techniques to obtain its convergence rates.

---

If the space has a boundary, then dimension counting result like Weyl's law for manifolds is only true with an appropriate boundary condition for finding the eigenfunctions. In general, different boundary conditions can lead to completely different function spaces for manifolds with boundaries. In the proof, we show that the projections of invariant functions onto the quotient space satisfy the Neumann boundary condition on the (potential) boundaries of the quotient space, thereby exactly characterizing the space of invariant functions, which can indeed be of independent interest.
To see how the Neumann boundary condition appears, consider the circle again and note that its eigenfunctions are the constant function do = 1, sin(k)), and cos(k0), with eigenvalues À k² k E N. Observe that every eigenvalue is of multiplicity two, except for the zero eigenvalue, which has multiplicity of one. For the quotient space S' /G, however, the eigenfunctions are just the constant function, sin (2k + 1)0), and cos (2k0). & E Z (note how roughly half of the eigenfunctions survived, as |G| = 2). particular, the boundary points (0, +11 satisfy the Neumann boundary condition, while the Dirichlet boundary condition fails to hold; look at the eigenfunctions at 0 = 7/2. More precisely, if we consider the Dirichlet boundary condition, then we get function space that includes only functions vanishing at the boundary points: o(T/2) = 6(37/2) = O. This clearly does not correspond to the space of invariant functions. We generalize this idea in our proof to any manifold and group using differential geometric tools (see Appendix A.5 and Appendix A.6).
In the above example, the boundary points come from the fact that the group action has non-tr con-trivial fixed points, i.e., (0, +1) are the fixed points. If the action is free, meaning that we have only trivial fixed points, then the quotient space is indeed boundaryless manifold. Thus, the challenges towards the proof arise from the existence of non-trivial fixed points.
Comparison to prior work. Lastly, discuss example the two-dimensional flat torus T = IR? /22/ which shows that the proof ideas in [5] are indeed not applicable for general manifolds even with finite group actions. For this boundaryless manifold, consider the isometric action G = {idc, }.. where T(0,, 02) = (0) + π, 02), and note that the quotient space T / is again torus. In this case, the eigenfunctions of T are the functions exp(iki x + ikky), for all k1 k2 E Z. with eigenvalue À = k2 + h.. But eigenfunctions of the quotient space are those with even 41. This means that some eigenspaces of T (such as those with eigenvalue x = 2(2n + 1) are completely lost after projection onto the space of invariant functions. This means that the method used in [5] fails to give a non-trivial bound here, because it relies on the fraction of eigenfunctions that survive in each eigenspace. Note that in this example, the quotient space is boundaryless, and the action is free.
4.3 Application to Finite-Dimensional Kernels
Applications of Theorem 4.4 are not limited to Sobolev spaces. As an example, we study KRR with finite-dimen dinte-diinsional PDS kernels K .M x .M- + R with an RKHS H (MM under invariances (the inclusion must be understood in terms of Hilbert spaces, i.e., the inner product on H. is just the usual inner product defined on L (MM),, making it completely different from Sobolev spaces). Examples of these finite-dimensional spaces are random feature models and two-layer neural networks in the lazy training regime. In this section, will relate the generalization error of KRR to the average amount of fluctuations of functions in the space and use our dimension counting result to study the gain of invariances.
To formalize this notion of complexity, we need to review some definitions. We measure fluctuation via the Dirichlet form &, bilinear form defined as
8(1.f2)) = J/ (Vofi(z), dvvol,)
(12)
for any two smooth functions f1. : M M + R. It can be easily extended (continuously) to any Sobolev space H (MM, 2 1. For each f E HMM,,, the diagonal quantity {(f.f) is called the Dirichlet energy of the function, and is a measure of complexity of a function. Functions with low Dirichlet energy have little fluctuation; intuitively, those have low (normalized) Lipschitz constants on average. Since E(af, af) = Ja [f] f), is more accurate to restrict to the case [|]l| = while studying low-energy functions.
7

---

One important example of a functions, which is generated by unite-dimensional G-invariant kernel K:
function space is the space of G-invariant low-energy
D-1
K (xr, y) = Σ Φe(x)))(y),
(13)
2=
for any y M. The non-zero G-invariant eigenfunctions de are sorted with respect to their eigenvalues (Appendix A.9). Clearly, is kernel of dimension D, and it diagonal in the basis of the Haplacc-Beltrann operator's s eigenfunctions. The RKHS of K is also of finite dimension dim(Ha) D and can be written as
D- Σ 20
Hg = f (M) ((
(f -- Li G).
(14)
To obtain generalization bounds, we will need to bound complexity measure of the space of low- energy invariant functions. As a complexity measure for finite function spaces H. S L (M, G), we use the Dirichlet energy f);
((H)
max {E(f.f) ( : $1).
(15)
JEH
For a vector space H. larger C(H) corresponds to having functions with more (normalized) fluctuation. Thus, L(V) is a notion of complexity for the vector space V. The following proposition shows how Ho is the simplest subspace of I. (MM) with dimension D.
Proposition 4.5. For any D-dimensional vector space H. S (M,, G)
((H) 2 AD-1:
(16)
and the equality only achieved when H Hg with dim(Hc). In particular, if ((H) co. then H is of finite dimension. The eigenvalues are sorted according to G-invariant eigenspaces (Appendix A.9).
Using the dimension counting bound in Theorem 4.4, we can explicitly relate the dimension of Hc to its complexity L(Ha). This will be useful for studying the gain of invariances for finite-dimensional kernels.
Theorem 4.6 (Dimension of the space of low-energy funetions). Under the assumptions in Theorem 4.4, one has the following relation between the dimension of the vector space Hg and its complexity L(Ho):
dim
Wa (2xrd
vol(M//)(((HL))02 (OCCCH)))))O+O()))))))))))))) =
(17)
where wa is the volume of the unit ball in TRd.
Given the above result, in conjunction with Proposition 4.5, we can obtain the following generalization error for any finite-dimensional RKHS C LMM)..
Corollary 4.7 (Convergence rate of KRR with invariances for finite dimensional kernels). Under the assumptions in Theorem 4.4, for KRR with an arbitrary finite-dimensional G-invariant RKHS H C (M).
E (R(f)-((C < Wa o² vol(M/G) P (f
(18)
(2T)d
n
where S. hides absolute constants. Moreover, the upper bound is minimax optimal if H. Ho (similar to Theorem 4.3).
Corollary 4.7 shows the same gain of invariances in terms of sample complexity as Theorem 4.1. Note that the asymptotic analysis for the above corollary, we assume that L(H) is large enough, allowing us use Theorem 4.6.
5 Examples and Applications
Next, we make our general results concrete for number of popular learning settings with invariances. This yields results for kernel versions of popular corresponding architectures.

---

5.1 Sets
When learning with sets, each data instance is subset {I1, 42 ...,, Im of elements xy E A, [m]. from a given space X. A set is invariant under permutations of its elements, i.e.,
(11, ... Fm (Nor -og. Fo.,
(19)
where a [m]] + [m]] can be any permutation. A successful permutation invariant architecture for learning sets is DeepSets [70]. Similarly, PointNets
a permutation invariant architecture for point clouds [53, 54J. To analyze learning with sets and kernel versions these architectures using formulation, assume sets of fixed cardinality m. If the space X' has manifold structure, then one can identify each data instance as point on the product manifold
= x
X x X ... x
(20)
The task is invariant to the action of the symmetric group Sm on M: each or E Sm acts on M by permuting the coordinates as in Equation (19). This action is isometric, and we have dim(Sm) and |.S. 1/m!. Theorem 4.1 hence implies that the sample complexity gain from permutation invariance is having effectively m! samples, where n is the number of observed sets. In fact, this result holds (for KRR) for any space X' with manifold structure.
5.2 Images
For images, we need translation invariant models. For instance, Convolutional Neural Networks (CNNs) [31, 28] compute translation invariant image representations. Each image is a 2D array (Ii.)) mn-1 ( such that ži E X for a space X' (e.g., for RGB, X' S R a compact subset). If X has a manifold structure, then identify each image with point on the manifold
m-1
M
X
(21)
where X is copy of X. The learning task is invariant under the action of the finite group (Z/mZ) x (Z/mZ) on M by shifting pixels: each (p. q) E (Z/mž) x (Z/mZ) corresponds to the isometry (#i,))")= (#i+p.itg)*) (the sum is understood modulo m). As result, the sample complexity gain corresponds to having effectively n x m² samples, where n is the number of images.
5.3 Point Clouds
3D point clouds have rotation, translation, and permutation symmetries. Tensor field neural networks [62] respect these invariances. We view each 3D point cloud as set {z ... 2m such that x; R /2' = [0, 1]3, which is essentially a point on the manifold M = (R3/Z35 / with dim(M) 3m. The learning task is invariant with respect permuting the coordinates of M, translating all points I; + x + r for some r E R2, and jointly rotating all points, I; + Qx; for an orthogonal matrix Q. We denote the group defined by those three operations G and observe that dim(G)
6. Thus, the gains of invariances in sample complexity are (1) reducing the dimension d of the space from 3m to 3m 6, and (2) having effectively n mn! samples, where n the number of point clouds.
5.4 Sign Flips of Eigenvectors
SignNet [37] a recent architecture for learning functions cigenvectors in a spectral decomposition. Each data instance is a sequence of cigenvectors (V1, 12, .2...... ... Um), E Rd. and flipping the sign of an eigenvector v; - - n2 does not change its eigenspace. The spectral data can be considered as a point on the manifold M (Sd-1)" (where gd-1 is the (d -ddimensional sphere), while the task invariant to all 2m possibilities of sign flips. The sample complexity gain of invariances is thus having effectively x 2m samples, where is the number of spectral data points.
5.5 Changes of Basis for Eigenvectors
BasisNet [37] represents spectral data with eigenvalue multiplicities. Fach input instance sequence of cigenspaces (V1, V2...., V,),, and each V, is represented by an orthonormal basis such

---

Vi,,,, (Rd) This is the Stiefel manifold with dimension dm, my (m Thus, the spectral data lie on a manifold of dimension
U........ (,,,,,2,,,,... as (ui,1,
dim(M) Σ (dm; - mm; + 1)/2).
(22)
The vector spaces' representations invariant to change of basis, ie., the group action is defined as (ii,1, U4...... V..,.) + (Qu,,1: Qu........ Qu,,,,) ) for any orthogonal matrix Q that fixes the
eigenspace V4. If G' denotes this group of invariances, then
dim (G)
Σ (m/(m; 1)/2).
(23)
Thus, the gain of invariances is reduction of the manifold's dimension to D mQ). For example, if m, for all then with d = pm get dim(M) d² { + 1) while after the reduction we have dim(M//G de - -dm. In this example, the quotient space is the Grassmannian manifold.
5.6 Learning Graphs
Each weighted, possibly directed graph on m vertices with initial node attributes can be naturally encoded by its adjacency matrix A E Rm Thus, the space of all weighted directed graphs on m vertices corresponds to compact manifold M C Rm if the weights are restricted to a bounded set. Learning tasks on graphs are invariant to permutations of rows and columns, i.e., the action of the symmetric group as A + AP for any permutation matrix P. For instance, Graph Neural Networks (GNNs) and graph kernels [64] implement this invariance. The sample complexity gain from invariances is thus evident; it corresponds to having effectively n x m! samples, where n is the number of sampled graphs.
5.7 Hyperbolic Spaces, Tori, etc.
One important feature of the results this paper is that they are not restricted to compact submanifolds of Euclidean spaces. In particular, the results are also valid for compact hyperbolic spaces; see [51] for a survey on applications of hyperbolic spaces in machine learning. Another type of space where results still valid are tori, i.e., T == (S'y², yd. Tori naturally occur for modeling joints in robot control [38]. In fact, Riemannian manifolds are beneficial in broader context for learning in robotics, e.g., arising from constraints, surveyed in [10]. Our results apply to invariant learning in all of these settings, too.
Conclusion
In this work, derived new generalization bounds for learning with invariances. These generalization bounds show a two-fold gain in sample complexity: (1) in the dimension term in the exponent, and (2) in the effective number of samples. Our results significantly generalize the range of settings where the bounds apply. In particular, (1) goes beyond prior work, since it applies to groups of positive dimension, whereas prior work assumed finite dimensions. At the heart of our analysis dimension counting bound for invariant functions on manifolds, which we expect to be useful more generally for analyzing learning with invariances. We prove this bound via differential geometry and show how to overcome several technical challenges related to the properties of the quotient space.
new
Acknowledgments and Disclosure of Funding
The authors extend their appreciation Semyon Dyatlov and Henrik Christensen for their valuable recommendations and inspiration. This work was supported by Office of Naval Research grant N00014-20-1-2023 (MURI MI-SCOPF), NSF award CCF-21 (TILOSS Al Institute), NSF award 2134108, and NSF TRIPODS program (award DMS- (MSS2002448)..
10

---

References
[1] Brandon Anderson, Truong-Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[2] A. K. Aniyan and Kshitij Thorat. Classifying radio galaxies with the convolutional neural network. The Astrophysical Journal Supplement Series, 2017.
[3] Thierry Aubin. Some nonlinear problems in Riemannian geometry. Springer Science & Business Media, 1998.
[4] Francis Bach. Learning Theory from First Principles (draft). 2021.
[5] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[6] Benjamin Bloem-Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, 2020.
[7] Glen Bredon. Introduction to compact transformation groups. Academic press, 1972.
[8] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.1377, 2021.
[9] Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2013.
[10] Sylvain Calinon. Gaussians on Riemannian manifolds: Applications for robot learning and adaptive control. IEEE Robotics & Automaaton Magazine, 2020.
[11] Yaiza Canzani. Analysis on manifolds via the Laplacian. Lecture notes, 2013.
[12] Isaac Chavel. Eigenvalues Riemannian geometry. Academic press, 1984.
[13] Shuxiao Chen, Edgar Dobriban, and Jane H. Lee. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 2020.
[14] Carlo Ciliberto, Francis Bach, and Alessandro Rudi. Localized structured prediction. In Advances Neural Information Processing Systems (NeurIPS). 2019.
[15] H. Dominguez Sánchez, M. Huertas- Poottas-ommany,, M. Bernardi, D. Tuccillo, and J. L. Fischer. Improving galaxy morphologies for SDSS with deep learning. Monthly Notices of the Royal Astronomical Society, 2018.
[16] Harold Donnelly. Bounds for eigenfunctions of the laplacian on compact riemannian manifolds. Journal of Functional Analysis, 2001.
[17] Simon S. Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R. Salakhutdinov, and Aarti Singh. How many samples are needed to estimate convolutional neural network? In Advances Neural Information Processing Systems (NeurIPS), 2018.
[18] Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. In Int. Conference on Learning Representations (ICLR), 2021.
[19] Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. In Advances Neural Information Processing Systems (NeurIPS), 2021.
[20] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In Int. Conference on Machine Learning (ICMI.,, 2021.
[21] Michael James Fenton, Alexander Shmakov, Ta-Wei Ho, Shih-Chieh Hsu, Daniel Whiteson, and Pierre Baldi. Permutationless many-jet event reconstruction with symmetry preserving attention networks. Physical Review D. 2022.

---

[22] Jan E. Gerken, Jimmy Aronsson. Oscar Carlsson, Hampus Linander, Fredrik Ohlsson, Christof- fer Petersson, and Daniel Persson. Geometric deep learning and equivariant neural networks. arXiv preprini arXiv:2 13926, 2021.
[23] Roberto E. González, Roberto P. Munoz, and Cristian A. Hernández. Galaxy detection and identification using deep learning and data augmentation. Astronomy and computing, 2018.
[24] Harrie Hendriks. Nonparametric estimation of a probability density on a Riemannian manifold using fourier expansions. The Annals of Statistics, 1990.
[25] Lars Hörmander. The spectral function of an elliptic operator. Acta mathematica, 1968.
[26] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018
[27] Shoshichi Kobayashi. Transformation groups in differential geometry. Springer Science & Business Media, 2012.
[28] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 2017.
[29] Olivier Lablée. Spectral theory in Riemannian geometry. European Mathematical Society, 2015.
[30] Hannah Lawrence, Kristian Georgiev, Andrew Dienes, and Bobak Toussi Kiani. Implicit bias of linear equivariant networks. In Int. Conference on Machine Learning (ICML), 2022.
[31] Y. LeCun, Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1989.
[32] Jason Sang Hun Lee, Inkyu Park, Ian James Watson, and Seungjin Yang. Zero-permutatioon jet-parton assignment using a self-attention network. arXiv preprint arXiv:2012.03552. 2020.
[33] John M. Lee. Introduction to smooth manifolds. Springer, 2013.
[34] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev
Arora. Enhanced convolutional neural tangent kernels. arXiv preprint
2019.
[35] Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-connected nets? In Int. Conference on Learning Representations (ICIR), 2021.
[36] Ziyao Li, Shuwen Yang, Guojie Song, and Lingsheng Cai. Conformation-guider molecular rep- resentation with Hamiltonian neural networks. In Inf. Conference on Learning Representations (ICLR), 2021.
[37] Derek Lim, Joshua Robinson, Lingxiao Zhao Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In Int. Conference on Learning Representations (ICLR), 2023.
[38] Puze Liu, Davide Tateo, Haitham Bou Ammar, and Jan Peters. Robot reinforcement learning on the constraint manifold. In Conference on Robot Learning (CoRL), 2022.
[39] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Hloem-Reddy On the benefits of invariance neural networks. arXiv preprint arXiv:2005.00/78 2020.
[40] Cong Ma, Reese Pathak, and Martin J. Wainwright. Optimally tackling covariate shift in RKHS-based nonparametric regression. The Annals of Statistics, 2023.
[41] Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 2012.
[42] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In Int. Conference on Learning Representations (ICLR), 2019.
12

---

[43] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Int. Conference on Machine Learning (ICML), 2019.
[44] Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya, On learning sets of symmetric elements. In Int. Conference Machine Learning (ICML), 2020.
[45] Andrew McRae, Justin Romberg, and Mark Davenport. Sample complexity and effective dimension for regression manifolds. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[46] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021.
[47] Subbaramiah Minakshisundaram and Ake Pleijel. Some properties of the eigenfunctions of the laplace-operator on Riemannian manifolds. Canadian Journal of Muthematics, 1949.
[48] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[49] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2019.
[50] Youssef Mroueh, Stephen Voinea, and Tomaso A Poggio. Learning with group invariant features: kernel perspective. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
[51] Wei Peng, Tuomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: survey. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2021.
[52] Peter Petersen, Riemannian geometry. Springer, 2006.
[53] Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3D classification and segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[54] Charles R. Qi, Li Yi, Hao Su, and Leonidas J. Guibas. Pointnet++:: Deep hierarchical feature learning on point sets in a metric space. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[55] Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In Int. Conference on Machine Learning (ICML), 2020.
[56] Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permuta- tion invariant/equivariant functions by deep neural networks. arXiv preprint 193.v91903.01939, 2019.
[57] Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group invariant/equivarian deep networks via quotient feature spaces. In Conference on Uncertainty in Artificial Intelligence (UAI), 2021.
[58] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. on Neural Networks, 2008.
[59] Kristof Schütt, Oliver Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. In Int. Conference on Machine Learning (ICML), 2021.
[60] Christopher D. Sogge. Concerning the Ip norm of spectral clusters for second-order elliptic operators on compact manifolds. Jourmal of functional analysis, 1988.
[61] Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of invariant classifiers. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
13

---

[62] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-ann and translation- -equivvariiiiiviaaann neural networks for 3D point clouds. arXiv preprint arXiv: 1802.08802. 2018.
[63] Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[64] S. Vichy N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 2010.
[65] Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. 2019.
[66] Rui Wang, Robin Walters, and Rose Yu. Incorporating symmetry into deep dynamics models for improved generalization. Int. Conference on Learning Representations (ICL.), 2021.
[67] Jared Willard, Xiaowei Jia, Shaoming Xu, Michael Steinbach, and Vipin Kumar. Integrating physics-based modeling with machine learning: A survey. arXiv preprint arXiv:2003.04919, 2020.
[68] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Int. Conference on Learning Representations (ICLR), 2019.
[69] Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 2022.
[70] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R. Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[71] Sicheng Zhu, Bang An, and Furong Huang. Understanding the generalization benefit of model invariance from a data perspective. Advances in Neural Information Processing Systems (NeurlPS), 2021.
[72] Aaron Zweig and Joan Bruna. functional perspective learning symmetric functions with neural networks. In /nt. Conference on Machine Learning (ICML), 2021.
14

---

A Preliminaries
A.1 Manifolds
A completely metrizable second countable topological space M that is locally homeomorphic to the Euclidean space (d)m((M) is called manifold of dimension dim(M), Sphere, torus, and R are some examples of manifolds. A Riemannian manifold (M,9) g)) a manifold that is equipped with a smooth inner product ! the tangent space T&M around each point E M. A Riemannian metric tensor g allows the use of the following two important tools in the study of manifolds: (i) the geodesic distance d y) between any points x, y E M, and (ii) the volume element d voly (zz) that defines a Borel measure on the manifold (on the Borel sigma-algebrs of open subsets of the manifold). The distance function and the volume element depend on the Riemannian metric tensor and make the manifold a metric- meetree space. The functional spaces on manifolds, such as (MMM), p E [1, oo), and the Sobolev spaces (M), $ 2 0, are defined similar to the Euclidean spaces.
A.2 Isometries
A bijection .M- - M is called an isometry of (M.g). if and only if dd((Tax), = dm(2; u) for all z, E M. The space of isometries of (M.g) forms a group under composition, denoted by ISO(M,g) g) or simply by ISO(M). By the Myers-Steenrod theorem, for connected manifolds, each T E ISO(M,9) is not only bijective but indeed smooth (i.e., infinitely many times differentiable) [52]. Moreover, (S) g) is a Lie group (i.e., a smooth manifold which
simultaneously a group) of dimension at most (im))))(dd((M)+))) Another characterization of 2 isometries on manifolds is based on metric tensors, where function M - M is an isometry and only if the pullback of the metric tensor g by T is itself, i.e., g = r"g. g. This means that т locally preserved inner products of tangent vectors. For the applications in this paper, whenever it is not mentioned, dim dimensionnl Riemannian manifolds (M, g) is smooth, connected, and compact boundaryless.
A.3 Laplacain on Manifolds
The Laplace- Beltreami operator is the unique continuous linear operator Ag (HMM) + (M() satisfying the property
Ju ((e))vo - (V (V)),, V (
(24)
for any 0, E (M)) This generalizes the usual definition of the Laplacian operator A 07 + defined on the Euclidean space Rd, which satisfies this property by integration by parts. The kernel of the operator A, includes the so-called harmonic functions. In the case of compact boundaryless manifolds, the only harmonic functions are constants.
The operator (~Ag) is elliptic, self-adjoint, and can be diagonalized in (MM) [12]. In particular, there exists an orthonormal basis {d)(s) of ('M starting from the constant function dn = 1 such that Agee + Ae O. for the discrete spectrum 0 = À < X < Xa < Note that eigenvalues appear in this sequence with their multiplicities. Let us call {oe(x)){² the Laplace- Beltrami basis for (.M) Using the above identity, for an arbitrary f (.2(M) with the expansion [[ Etzo Kf, Φe) L we have
f L (e) (N and (M²) A, = - >e(S, de) the and
V NolliAA = / (V (v)f(x), V (=f(x)),
(25)
-/ [ [())Ag
(26)
Σ
(27)
2=2
whenever the sums converge.
15

---

A.4 (Local) Weyl's Law
is known that the Laplace-Beltee Beltrami spectrum can encode many manifold geometric properties, such as dimension, volume, etc. However, it is also known that isospectral (non-isomorphee manifolds exist. Still, it provides rich information about the manifold. Let us denote the set of distinct eigenvalues of manifold by Spec(M) == {Ao, .I,...} C IR
Weyl's law characterizes the asymptotic distribution of the eigenvalues in closed-form formula. Let us denote the number of eigenvalues of the Laplace-Beltrann operator up to À as N()) == # d I A}.
Proposition A.1 (Local Weyl's law, [11, 25, 60D. Let (M.g) denote an arbitrary dim(M)- dimensional compact boundaryless Riemannian manifold. Then, for all x E M.
:= Σ (de(z))
(M) vol(M))dim(MM) + +O (2r)
diml
(28)
P.ASAA
2//2 as \ + oo, where wi -1)-1) is the volume of the unit d-ball in the Euclidean space TR. The constant in the error term is indeed independent of x and may only depend on the sectional curvature and the injectivity radius of the manifold [16]. As a byproduct, the following 1 upper bound also holds:
max max | = =
(29)
A MEM
By definition, (A) = JM N₂ (A)d and thus, while the above result is called the local Weyl's
law, the traditional Weyl's law can be easily derived as N(A) (2rrddim(M) vol(M))ding din(M//22
Waim(M)
O(A (im(/M)) ). For compact Riemannian manifolds (M,g) with boundary, define the eigenfunc- tions of the Laplace-Bellne Beltrami operator (i.e., the solutions to the equation Ag + AØ = 0), one has to consider boundary conditions. For the Dirichlet boundary condition (i.e., assuming the solution vanishes on the boundary), or the Neumann boundary condition (i.c., assuming the solution's 's gradient vanishes on the outward normal vector at each point of the boundary), the above claim on the local behavior of eigenfunctions still holds.
The asymptotic distribution of eigenvalues allows us define the Minakshiisundaaam-PPlijee zeta function of the manifold (M,g) as follows [47]:
20
dim(M)
(M = Σ 1
X dN(A): 3(s)
(30)
2
0+
where the sum converges absolutely by Weyl's law. Note that the integral must be understood as Riemann- -Steeltje integral. The zeta function can be analytically continued to a meromorphic function on the complex plane and has a functional equation. By integration by parts,
ZM((s) 1 X dd
(31)
= - -10 N(A)(-s)A
(32)
= l N(J)A==1da.
=8 Jot
(33)
by N(A) ((Xilm(M)2) and the assumption 3(s) dim(M)
For more information on the spectral theory of Riemannian manifolds, see [29].
A.5
Quotient Manifold Theorem
This part and the next subsection review some classical results about group actions on manifolds
(mostly from [33, 27, 7D. Let G be an arbitrary group. The action of G on the manifold M is
mapping 0 G x M + M such that O(idg..) idy and (TTTT..)) ((T,, ((T,.)) for any
16

---

71,72 E G. In particular, any group action gives a G-inndeed set of bijections on M with respect to the group law of G. For example, ISO(M) acts on M by the isometric transformations (which are bijections by definition).
For each M, the orbit of x is defined the set of all images of the group transformations on the manifold:
[x] == (0(T,z) E M: T.
(34)
Also, for any x E M, define the isotropy group G2 isotropy group Gz, subgroup of G, includes all the transformations T E G which have M as fixed point. The set of all orbits is denoted by M/G and is called the orbit space (or sometimes the fundamental domain) of the action on the manifold:
x). In other words, the
M/G = [(x] : x M}.
(35)
It is known that M/G admits unique topological structure coming from the topology of the manifold, making the projection (or the quotient) map π : .M- - M/G continuous.
However, M/G is not always a manifold. For example, if M = Rd and G (R), then the resulting orbit space M/G G' is not Hausdorff. Even in cases where it is a manifold, the orbit space M/G may have boundaries while M is boundaryless. For example, consider the action of the orthogonal group ((d)= := {A e GLa(R): A" A AT La} on the manifold M Fd where the orbit space becomes M/G = Rzo. For the purpose of this paper, boundaries are important and affect the results drastically.
The quotient manifold theorem gives a number of sufficient conditions on the manifold/group. such that the orbit space is always manifold. To introduce the theorem, need to review few classical definitions as follows.
A group action is called free, if and only if it has no non-trivial fixed points, i.e., ((T, o x for all T * idg (equivalently, G2 = } } for all æ E M). For example, the action of the group of linear transformations ((r,x)
+ r, for each x, r E RRd, on the manifold TR is a free action. An action is called smooth if and only if for each E G, the mapping 0(T, .)) : M - MM is smooth. An action is called proper, if and only if the map (((T,r), : G x M + M x M is a proper map. As a sufficient condition, every continuous action of a compact Lie group G on a manifold is proper. To simplify our notation, let us define T(z) == ((T,
Theorem A.2 (Quotient Manifold Theorem, [33]). Let G be a Lie group acting smoothly, freely, and properly on a smooth manifold (M,g). g). Then, the orbit space (or the Sundamental domain) M is a smooth manifold of dimension dim( - dim(G) with unique smooth structure such that the projection (or the quotient) map M M/G is smooth submersion.
Corollary A.3. Suppose M is connected smooth compact boundaryless manifold. Then, the isometry group ISO(M) a compact Lie group acting smoothly on M. Thus. if G is a closed subgroup of ISO(M), then the action of G on M is smooth and proper. In addition, this action is free, then the orhit space M/G becomes a connected closed (i.e, compact boundaryless) manifold of dimension dim(M) dim
Furthermore, assuming (M. g) is a Riemannian manifold, there exists a unique Riemannian metric g such that the projection map (M,g) (M/G, g) is a Riemannian submersion.
There is indeed a natural way to interpret these results. Given a manifold (M. g). the orbit space is somehow the shrinkage of the manifold to represent exactly representative from each orbit, and the metric ğ is just identical to the original metric if the tangent lines survive; otherwise, the tangent lines are killed, and the inner product defined by ğ is zero.
A.6 Principal Orbit Theorem
The quotient manifold theorem is, however, restricted to free actions. Unfortunately, this assumption is generally necessary prove that the quotient space is compact boundaryless manifold. In the lack of freeness, it is still possible to show that the quotient space is almost a manifold (possibly with boundary). First, let us introduce few definitions. Two isotropy groups G5 and Gy are called G. This is relation on the
conjugate (with respect to G), if and only if - Gy for some
17

---

manifold, and the isotropy rype of any x E M is defined as the equivalence class of its isotropy group, denoted as [G.]. Since all the points on an orbit have the same isotropy type (by definition), one can also define the isotropy type of an orbit in the same way. Given the conjugacy relation, partial order can be naturally defined as follows: H1 3 H2 if and only if H1 is conjugate to a subgroup of H2. Since the definition is unchanged modulo conjugate groups, one can also restrict the partial order to the conjugacy class of subgroups. This allows us to define a partial order on orbits as well: for any two orbits [x]], [y]. we write [x]] - [y] if and only if Gy I Gg. For example, if G2 {dda). then wv] S [x]] for all y E M..
Given the above formal definitions, the quotient manifold theorem assumes that all the orbits have a unique maximal orbit rype, namely, the orbit type [[ida]]. By removing the freeness assumption, however, there might be several orbit types that are not necessarily comparable with respect to the partial order. However, the principal orbit type theorem shows that there always exists a unique maximal orbit type, where when the action is restricted to those orbits, it defines a Riemannian submersion (thus the image is a manifold), and moreover, the principal orbits (those orbit with the maximal orbit types) are dense in the manifold M. This shows that we almost get nice space, which suffices for our subsequent proof' in the next sections.
Theorem A.4 (Principal Orbit Theorem). Let G be a compact Lie group acting isometrically on Riemannian manifold (M.g). Then, there exists an open dense subset Mu S M, such that [z] 2 M for all x E MM and y E M. Moreover, the natural projection π : -M + Ma/G S M/ is Riemannian submersion. Also, the set Mo/G S M// is open, dense, and connected in M/G.
Corollary A.5. One has the decomposition
M/G = U Mn//G,
(36)
[M
is a submanifold of M. The disjoint union is taken over all isotropy rypes of the group action on the manifold. The map x : .M + Mun /G is a Riemannian submersion; therefore its image is manifold. By application of the Slice theorem, one can observe that only finitely many isotropy types can exist when G and M are both compact. Thus, the disjoint union is indeed over finitely many precompact smooth manifolds. Among those, the principal part MiHaa/G / is dense in M/G. where [Ho] is the unique maximal isotropy type of the group action.
where
Mo/ Bo/G=
== ==
Intuitively, the above corollary shows that the quotient space can be decomposed to finitely many "pieces," and each piece has nice smooth structure. In the case of a free action, the decomposition above reduces to just one "piece" with the unique trivial maximal orbit type (i.e., having a trivial isotropy group). The dimension of each "piece" MIHI/G can be computed as
dim(Mpn/GG) = dim(M)- - dim dG) + dim(H).
(37)
The effective dimension of the quotient space is then defined as d dim dim /G) = dim(Mo/G) G) dim(M) dim(G) + dim(Ho),
(38)
where [Ho] is the unique maximal isotropy type of the group action.
A.7 Isometries and Laplace-Beltrami Eigenspaces
In Weyl's law, the eigenvalues are counted with their multiplicities. Let us define VA as the eigenspace of the cigenvalue À with the finite dimension dVm). Then, (N = Exex dim (.)).
As well-known fact from differential geometry, the Laplace-Beltrami operator A, commutes with all isometries 7 E ISO(M). Thus,
Agoe + x 0 + A oT) + de o7) O.
(39)
This means that the eigenspaces of the Laplace-Beltrami Beltrami operator are invariant with respect to the action of the isometry group the manifold. Corollary A.6. (2(M) = +xeSpec(M)) Vx, and the isometry group of the manifold ISO(M) (and thus all its closed subgroups) acts each eigenspace Vx.
18

---

Now consider an arbitrary closed subgroup G of the isometry group (S)(M). Then G acts on the eigenspaces of the Laplace-Belrrami Beltrami operator and each G corresponds bijective linear transformation / f denoted as - VA + Vx. There is a natural way to extend this operator into the whole space (MV so one may consider 7 (M) (MM.. Since 7 is an isometry, for any Va.
|Ti = J..
M [x10())]
(40)
[v(=)\
(41)
ll
(42)
=1,
(43)
since d volg is invariant with respect any isometry T E G. This shows that the bijective linear transformation r is indeed a representation of the group G into the orthogonal group ((dim for each eigenvalue A.
In this paper, we are interested the space of invariant functions defined with respect to an arbitrary closed subgroup G of the isometry group (S).
Definition A.7. The space of invariant functions with respect to a closed subgroup G of the isometry group (SM) defined as
L (M, {
C LM)
(44)
as closed subspace of (2M)).
Let dr denote the Haar measure (i.e., the uniform measure) associated with a closed subgroup G of the isometry group (SO(M). Let the projection operator Pa (2M + Liv (M, G) defined as f(x) - Sa o (x)) = -a T* (z))TT. Claerly, I E (M, G) and only if f E ker(1 Pa).
Proposition A.8. For any closed subgroup G of the isometry group ISO(M), the following decom- position holds:
L (M, kee(lrr -P))
(45)
n
ker(1 - -x,)
(46)
XESpec(M) tEG
VA,G:
(47)
XESpec(M)
where each Vx,G is linear subspace of Vx defined
Vx.G {1 :
(48)
= n ker(I - -)).
(49)
FEG
Clearly, dim S dim(V.).
Moreover, the (restricted) projection operator Pa VA - Vx has the image Vx. and can be diagonalized in a basis for V,, such as oxe E Vx, f = 1,2.... dim(Vx), such that for each
= Ei dim((V))
acox. E Vx
JEVAG
=
ve dim(V,,c) as
(50)
dim((s.c)
Pxaf= =
Σ
aeox E VxG-
(51)
t=1
Due to its simplicity, we omit the proof of this proposition. We always consider the diagonalized basis in this paper, it always exists for appropriate eigenfunctions.
19

---

A.8 Reproducing Kernel Hilbert Spaces on Manifolds
smooth connected compact boundaryless Riemannian manifold (M.g) g) is indeed a compact metric- measure space, and kernel K .M x M + I can be thought of as a measure of similarity between points on the manifold. We assume that K is continuous, symmetric, and positive-definite meaning that K ((x, v) = ((v,)) 2)) and Σij=1 0:0; K (z4, Mj) 2 0 for any a; E R, J. Uj E M,, = 0 (assuming the points Hilbert
1, ........ n. and the equality happens only when 01
on the manifold are distinct). The Reproducing Kernel Hilbert Space (RKHS) of K space H. S (2M that is achieved by the completion of the span of functions k(., v) E H. for each y E M,, satisfying the following property: for all f E H. f(z) = (f., ((..)) Associated with the kernel K, there exists an integral operator K. (M) - (M) defined as K(())
SM ((x, (y)( volg(y) It can be shown that K can be diagonalized in an appropriate orthonormal basis of functions in L (2M (Mercer's 's theorem). Indeed, with a number of appropriate assumptions, it can be diagonalized in the Laplace-Beltramt spectrum.
Proposition A.9. Consider symmetric positive-definite kernel K X M + R. and assume that K (M x M) satisfies the differential equation gg (K (xx, y)) = Ag v)). Then, K can be diagonalized in the basis of the eigenfunctions of the Laplace-Beltrami Beltrami operator; there exist appropriate pt 2 0, L 0, 0,1,.... such that
K(I,9) Σ ())e())
(52)
F-
where dr, E = 1,. an orthonormal basis for (2M such that d + dede = 0 for each L.
Proof. Note that K((b(())) = JM K(x, vol, Therefore,
g.z (K(())) = Ag ( K(I, ((
(53)
M A ((
(54)
M (erKK(e,,)))(())dvvo
(55)
[ K(x, ()
(56)
de I K(I,
(57)
(58)
where we used the symmetry of the kernel, the regularity condition of the kernel (allowing the interchange of the differentiation and the integral sign), and also the self-adjointness of the Laplace- Beltrami operator. Now since K(ěr) satisfies the equation A, (X(())) + Xx(();) = O, we conclude that K((e) is indeed an eigenfunction with respect to the eigenvalue de, or equivalently K((+)) VA,- In other words, Vx. À E Spec are the invariant subspaces of the integral operator associated with the kernel. This means that one can choose an appropriate basis of eigenfunctions in each eigenspace, such that the kernel is diagonalized in each eigenspace (Mercer's theorem).
Remark 1.1 While Proposition A.9 holds for kernel K CR(M M). it can be shown that it holds under a weaker assumption that K just continuous. The identity (K(,(K(()))) Ag (K(a (x, y)) should then be understood as the identity of two distributions.
In this paper, we always consider the diagonalized kernels in the Laplace-Beltramt spectrum. An example of kernel of this form is the heat kernel with μı erett E R. Given a diagonalized kernel K(x,) v) = 000 (z) one can explicitly define the RKHS associated with K as
H = {s Σ
lae??
}c}
(59)
F=
20

---

with the fnner-produe
Σ t=0
Beos
(60)
H
Nz
t=0
t=
where the sum is considered convergent whenever it converges absolutely. The feature map is therefore given as 4 K (z..) Et=g (10) for any M. The covariance operator E : H. - H. is also defined as Σ = Ez~z 4 8. Φx where the expectation is with respect to the uniform sample I E M (with respect to the normalized volume element dp vol( volg(1), It is
worth mentioning the identity [ # =
[[] Also note if f* = Ez 6x) (M))) then the effective ridge regression estimator (Equation 4) is given by the closed-form formula
feft
Hi (f (z) L()
(61)
Me +
t=
A.9 Invariant Kernels
A kernel K :M x M + R is called G- G-invariant with respect to closed subgroup G of ISO(M). if and only if (x, y) ((T(r),7'()) for any T, E G. Equivalently, one has K (z, y) [[<=),, [v]) for any T. E M.. In the previous section, it is observed that K can be written as K(2 v) Ei= ( (eee))().) under a few conditions. Since K is G-invariant, a new basis of eigenfunctions exists that allows a more compact representation of the kernel.
Proposition A.11. For any closed subgroup G of (S),M), consider a symmetric positive-definite G G-inaariant kernel K -M M R. and assume that K CM M) satisfies the dif- ferential equation Ag. (K (2, v)) (g,(((zz,))) v)). Then, K can be diagonalized in the basis of eigenfunctions of the Laplace-Bettrami
Beltrami operator:
dim(Va,a)
K(r,y)=
Σ
Σ
(62)
(MSpne(M)
where the functions 6x.8 for any Spec(M), and any l dimm())) form a basis for
1,2 (M) such that Ag( + ((xxe) for each f, Moreover, the functions Φx to for any À Spec(M), and any l...., dim((a.c). form orthonormal basis for L (M, G).
Therefore, the RKHS of a G invariant kernel K can be defined as
dim((x,a)
dim(Va.c) laxpl
H =
Σ
axcore::
Σ
< c0)
(63)
(M
XESpec(M)
with the inner-product
dim(Vs,c)
dim(Vs.e)
dim(V
axx.
Σ
B
Pxye
ASpec(M)
XESpec(M)
(64)
Whenever G is the trivial group, the above identities reduce to what is proposed for general (not necessarily invariant) kernels on manifolds in the previous section. Once again, the assumption K E C² x M) can be weakened to just the continuity of K.
A.10 Sobolev Spaces of Functions on Manifolds
For any integer & 2 O, the Sobolev space H²M) is the Hilbert space of measurable functions on M with -quare-integrabl partial derivatives' to order More generally, (M)( denotes the Banach space of measurable functions with T.P bounded partial derivatives up to order s. As
'The partial derivatives manifolds are defined locally in each coordinate.
21

---

observed in [24]. one can define the Sobolev space (M) C (MM using the eigenfunctions of the Laplace-Beltne Beltrami operator as
(MM == {
f
acoe: IIf =
(a) < oo].
(65)
1=
The inner-product on H. (M) is defined as
Σ
max(1, A3)a
(66)
HM(M)
E=
This makes H²M an RKHS with the Sobolev kernel defined as
dim(Vs)
(uo(c)(E,,)) = Σ
Σ
min(1, (()
(67)
AESpec(M))
For G-invariant functions, as before, the above sum must be truncated to dim(Vx.a) instead of (Vx). Therefore, Hiny (M) (M) (M, G) is well-defined.
We note that 7 (M) includes only continuous functions when 8 > d/2. Moreover, contains only continuously differentiable functions up to order A: when d/2 + k; see the Sobolev inequality:
Proposition A.12 ([3), Sobolev inequality). Let 1 3 3 === & with e 0 and q 2, where d is the dimension of the smooth compact closed manifold M. Then,
[I S CCI///eeem The constant C' may depend only on the manifold and the parameters but is independent of the function f (M.)
(68)
B Proof of Theorem 4.4
We first prove Theorem 4.4 for the cases that the group action on the manifold is free (Proposition B.1), and then we extend to the general case. We use the preset notation/definitiions introduced in Appendix A (specifically, Proposition A.8) in this section.
Proposition B.1. Let (M.g) g) be smooth connected compact boundaryless Riemannian manifold of dimension dim(M), Let G be Lie subgroup of ISO(M) of dimension dim(G),, and assume that G acts freely on M (i.e., having no non-trivial fixed point), and let == dim(M) dim(G) denote the effective dimension of the quotient space. Then,
dim(Vs .))
N2(A;)= = Σ
Σ
(ox,e(1)
Wa (2xrdd vol(M/G)4*++ + +
(69)
USA
as A CO, where Wa
r(g+15 is the volume of the unit d-ball in the Euclidean space Te.
4/2
Remark B.2. Note that the above proposition provides a much stronger result than Theorem 4.4; local. Observe that N(A; G) IMy NA(A; G)d vol, and thus integrating the left-hand side of the above equation proves Theorem 4.4 for the special case of free actions. We will later prove the same local result (Fquation (69)) for the general smooth compact Lie group actions manifold, presuming the assumptions Theorem 4.4.
Proof of Proposition B.I. By the quotient manifold theorem (Theorem A.2) and Corollary A.3, the orbit space M/G is a connected closed (i.e, compact boundaryless) manifold of dimension dim(MM) dim G). Let Ag and A3 denote the Laplace-Belraand Beltrami operators on M and M/G. respectively. where is the induced Riemannian metric on M/G from g. Consider two arbitrary smooth functions ø M - TR and Ø M/G + R such that Φ(x) = p([z)). Note that Ø is smooth on M, if and only if is smooth on M/G, and also, is invariant by definition. Fix an arbitrary X. We claim that
A + x²= =0 + A - =0
(70)
22

---

Given the above identity, the desired result follows immediately by an application of the local Weyl's law (Proposition A.1) on the manifold M/G of dimension d dim(M) dim(G).
To prove the claim, we only need show that - AgO. First assume that G is finite group (i.e., dim(G) 0). Note that in local coordinates (z' x²2 ...., Mi) we have
g
de V
(71)
However, the projection map π M + M/G is Riemannian submersion, with differential du, T.M- + To] (M/G) being an invertible linear map from a dim(MM))dimensional vec- tor space to another (on(MM)diimension vector space. This shows that the local coordinates are also simultaneously some local coordinates for M/G,, and since I is induced by the metric g. the result holds by the above identity for the Laplace- -alatcc-ee operator.
(xr (x²,=² _.?.... ,.....,ddim(M
Now assume dim( GG) > L. In this case, for the projection map .M- M/G, the differential map d T.M- + Ti is a surjective linear map from a dim(M dimensioonl vector space to (Mi - (iim(G))-dmmnntle dimensional vector space. Indeed, Ty-M- ker(dTg) o ker (dTz). with respect to the inner product defined by g. This means that with an appropriate choice of local coordinates such as (x x², ..,,... x dim(M) around a point x E M, satisfying
91 9
3 à 0)) a
= iffi=}..
(72)
0,
for any i,j E
we have S. ker (dTxz) for any
dim(()
dim(G), G), and 8. oy local coordinates to the first dim(M) - dim (G) elements is assumed to be some local coordinates for M/G. This always possible for an appropriate choice of local coordinates.
E ker(dTa) for any i > dim(M) - dim(G) In particular, the restriction of the
In these specific local coordinates, by definition,
dim([M)
A cb
(73)
2=1
(im(M))dimmt
A
Σ
02
(74)
Note that 0.55 -. for = 1,2.... dim (M) - GG). Thus, the proof is complete if we show 0, = 0, for all dim(M) dG), for a neighborhood around x in the local coordinates (2dim((M)-dmm(())
x MM), while the other coordinates are kept the same as x. But note that for any x' sufficiently close to x with the same coordinates [x'] = [z)]. by definition. This means that x(x) = <(x') and this completes the proof.
(x:1, x². :....... (pdlm(MM-dii(G))) one has
To extend Proposition B.I to general smooth compact Lie group action G, we need to use the principal orbit theorem (Theorem A.4) and its consequences (see Appendix A.6). Again, we prove that the generalized local result (Equation (69)) holds, presuming the assumptions in Theorem 4.4.
Proof of Theorem 4.4, According to Corollary A.5, one has the following decomposition of the quotient space: M/G = L| M G. other words, the quotient space is the disjoint union of finitely many manifolds, and among them, Ma/ G is open and dense in M/G. As first step towards the proof, we show that AgΦ Ago for any two smooth functions & Mo + R and Ø MoMo -> IR such that xxx) ò( (((z)), for any Mo and [x: Mo/G. However, the proof of this claim is exactly the same as what is presented in the proof of Proposition B.1; thus, we skip it.
Recall that the effective dimension of the quotient space is defined as d dim(M /G) dim(Mo/GG /G) = dim(M) dim(G) (G) + dim Ho), where [Ho] is the unique maximal isotropy type (corresponding to Mo). We claim that there exists a connected compact manifold (possibly with boundary) M S M/G such that (1) it includes the principal part, i.e., M 2 Ma/G, and (2) the projected invariant functions M satisfy the Neumann boundary condition on its boundary ((M).
23

---

More precisely, the second condition means that for any two smooth functions Φ Mo - R and Φ .Mo G - I. such that <(x:) = ((xx) ), for any x E Mo and [x] E Mo/G, the function Φ satisfies the Neumann boundary condition on ((M). Given this claim, by the local Weyl's law (Proposition A. the proof is complete.
We only need to specify the manifold . and prove that each projected invariant function on it satisfies the Neumann boundary condition. Indeed, the construction of the manifold M follows from the finite decomposition of the quotient space M/G = LI M M//G..G...... /G. Moreover, we can assume that the boundary of . is piecewise smooth. Let [x)] E ((M) be a boundary point (in the interior of smooth piece of the boundary). We claim that
e is G-ivarriant on M = (V 3 (())) = O,
(75)
for any smooth Φ : .M- - R, where ((x) = ((x)), and this completes the proof. Note that (aa E (MM is the unit outward normal vector of the manifold M at [x)]. To prove the claim, we write (M) = span(f)=)) @ Hi] for an orthogonal vector space H[x)- But H|] = (MM) Also, in neighborhood N around [x]] in ((M). for each ly] E W,, we have the smooth identity (Pt) T-] o (w)) = y for some Ply) T-] G, such that (P%) 1 7pr Plu)) does not belong to isotropy groups of Mo/G near [zr]. Without loss of generality, we assume that P[s] = idg.
Now consider a geodesic on M starting from E M with unit velocity such as r(t) with ((0)
and [z) (0)) - f/]=]- Note that [x] & @(M) for small enough 1 E (0, e). and thus it belongs to Mo/ G. But it is simultaneously "on the other side" of the particular fundamental domain of MM/G around [z:]. meaning that [mw] (T()) is necessarily curve starting from [ar] towards the inside of the fundamental domain. In particular, since Twl is an isometry (and thus a local isometry), we necessarily have (1m² o (0) = -212 (note that in this step we clearly use the explanations in the
previous paragraph). Now by considering the function @ o 7 = & o [x] o ry on the interval E (0, e). we get
(V)((=x), à()))a = (Vg)((x),
=
(Vgo([a)), = O,
(76)
and this completes the proof.
C Proof of Theorem 4.1
In this section, we use Theorem 4.4 to prove Theorem 4.1. Let us first state a standard bound in the literature holding for any RKHS.
Proposition C.1 ([4), Proposition 7.3). Consider the KRR problem in an RKHS setting, and let fproj denote the orthogonal projection of f* on the Hilbert space H. Assume that K K(x,x) x) S. R2 for any x E M, S R2, and n 2 An² (1 + log( R², )). Then,
E(R(f) -R(Si R(Frroj)I ) s 16 0²
tr((E + 1/
(77)
24
+ 16 inf {llf - Sfro 1IE + mllffibe + JCH
llf 11=(0)))
(78)
n²
where the expectation is over the randomness of the dataset S, and Σ = Ernn
H oz $2]
is the
covariance operator with the feature map 4z = Eizo (r)e(r)0 for any x E M.
Note that firi = f if the closure of H. with respect to the L'(MM)norm is L (M,G). In the Laplace-Beltrami
Beltrami basis, E is diagonal with the diagonal elements (E),,e = μe for each f. Note that the first and second terms in the above upper bound are known as the variance and the bias terms, respectively. Also, while the bound holds expectation for a random dataset S, assuming e, 's are sub-Gaussiaa one can extend the result to high-probabiln inequalities. However, for the brevity/clarity of the paper, we restrict our attention to the expectation of the population risk.
bound using standard concentration
24

---

We need to have an explicit upper bound for R to use the above proposition. Although the problem essentially homogenous with respect to R. for the sake of completeness, we explicitly compute a uniform upper bound on the diagonal values of the kernel in terms of the problem's 's parameters.
The goal is to first check that the two conditions R oo and n 5R" (1 log(
R )) satisfied. 1
The latter condition is indeed satisfied when 1) 2 5 log(n), Note that if PA. + for any X, l with = 1,2,....- dim (V),a), then any G-invariant function f E E C Luv (M, G) is in the closure of H. Indeed, in that case the closure of H. with respect to the (M) norm includes L (M, G).
n
C.1 Bounding K (z,
We start with the definition of Rt; for any M, we have
dim(Va,a V)
K ((x,,) x) = (D2, Da)H
Σ t=1
px)
(79)
(ES
By the local version of Theorem 4.4, we know that (A; = ExSa Eie Wiin(V {x)
wi vol(M//)x4 + CM/aA" " for an absolute constant CM/GS where d denotes the effective (2w)a
dimension of the quotient space. Therefore, ux,e S u(A) for a differentiable bounded function (()), for any X, e, then
K(x, x) S [_m u(A)dNN(AAGG)
(80)
- lim ((O (aatoo::)--[NNNCCNCC N=(A:G)u'(A)a
(81)
( Wd
vol(M/G) ( x f- X(-ni)2
(82)
(2TT)d
vol(M/G) 1- xd12- + Cmjo CMmj fr ((u-1)/2-1u(A)a)
( Wa
(83)
(2m)d
vol(M/G) ((Mu)(a/2)) + Cmjo (MM)((Mu((d 2 (2T)d
d Wa
(84)
where (a) and (c) follow by integration by parts, and (b) follows from Theorem 4.4. The Mellin transform is defined as [sMu[(s) == Ls (t-lu(t)dt. Also, integration with respect to dN,,,t G) must be understood as Riemann -tanlle-ss integral.
C.2 Bounding the Bias Term
We have already observed that the function achieving the infimum is
dim(Vx.c)
fer
Σ
Σ
PAx
(f" (x))
(85)
Px. +
AESpeo(M)
Note that clearly far E H for 1j > O, we can explicitly compute || < 00. Also,
dim(V2.c)
.proj
Σ
(ux, + (od
(86)
XESpec(M)
1=1
Thus.
16 inf {11s- /iros JEH
m (l= +
16]] - Siros 1 + 16rll
(87)
diun(Vs.a)
= 16
Σ
Hre ( (Viroji
@x.e (88)
M)
E=1
25

---

dim(Vs.c)
Mar prrt + ( (2.e) (89)
1 Ha.t
+ 16n
M)Spec(M)
dim(Va.c)
11p + -11s)
= 16
E
(Xx. (uxe++)) + n)?
(prooj ox.e)
(90)
()Spec(M
t=1
dim(Va,a)
1
161
Upsoss Op
(91)
Pr,t + 1)
()Spoc(
C.3 Bounding the Variance Term
We need to compute the trace of the operator (E + 11)- But this operator diagonal in the Laplace-Bed Belllce- basis, and thus we get
dim(Va.c)
16 22
11(=+n1)~'2]
PA, PA,E
(92)
"
n
+ 1)
AESpec(M)
t=1
C.4 Bounding the Population Risk
Now we combine the previous steps to get
dim(Vs,a)
B(R(f) RR( S 16 o²
PAA Px, +
(93)
n
(MSpec(M)
t=1
dim(Va,.)
uxLe (
+ 16n
m) Uprojj (x
(94)
(ESp
8=1
24
+ n
| 2 (M))
(95)
which holds when R < oc: and 2
3 log(n)
We are now ready to bound the convergence rate of the population risk of KRR for invariant Sobolev
space Hig (M) (See Section A. for the definition). this case, Mxx = u(A) min(1, A=*) for each X, l. Therefore,
(Mu)dd/2) = / min(1, x 10101- ldl < +1+ d/2
(96)
Similarly, (Mu)((d- - $ 3-(d-11/2 Thus, using the analysis in Section C.I, we get
(H, S R² = Wd
(2x)d (M(M)))(1/2))
d/2
(97)
s-d/2
1
CMIG -- - 1
(98)
In particular, R < 0o if d/2. We now compute the bias and the variance terms follows, Let us start with the variance term:
dim Σ
16 02
min(1, dN(A: G)
16
=
(99)
n
min (i +
XESpec(
-
< 16
N(1:G) + 16
dN G)
(100)
n J
x-+
16
N(1:G) 16
G)
(101)
n
1+ m
26

---

(
0²
o² lim
N)
16- 0² N(:
16
G(:
+
(102)
n
Te. X
1 1/1
7 1 1+
2²
8T
16
N(
(1 + n)2=12 dd
(103)
71
(6)
0²
N(1G) - -16 o²
J N(A; G) (1 + mz1m13 dd
16
(104)
1
1
1 7
8²
N(1:)) + +16 r² Wd vol(M/G)sn
1=11
(
16
dd
(105)
1+
n (2T)d
(1+ n2o3
CMIOST J 1(d-1)/2
1011
+ 16
(1 + m)20)2 ds
(106)
n
16 0² wd vol vol(M/G)s) (2
) (0) X4/2-a-1
S 16
(1;
17 dx
(107)
+ 16 0² CMraST
(
dd,
(108)
1+ 2
n
where (a) follows by integration by parts, (b) follows by limx
N(A:G) 1+1AA-
since > d/2, and
(c) follows from Theorem 4.4. Note that integration with respect to d.N G) must be understood as
Riemann-Sticltjer integral. By change of variable in the integrals as t Xn/ we have
dd/2+s-1 1 dd dx= =
(04d/22211)11 1/s J.
44/2+811
1 dt < 7 (s+4/2)
(109)
2x - d
We can similarly evaluate the other integral and conclude
dim(Va.c)
MAL S 16 02 ()IG)
16
Σ
Σ
(110)
n
+1
n
AESpeo(M)
t=1
+ 16
sa²
Wi
vol(M/G)n)
(111)
(2s d)n (2T)d
so²
CM/GnT--600 (0+(d11))2
+ (2s - d + 1)m
(112)
One can also use the bound N(1:G) < [2=] vol(M/)) + Cyya to simplify the upper bound.
Note that Mproj = since the closure of Hin (M) with respect to the (2(MM)norm -oom is the whole space Liw (M, G). Let now analyze the bias term by noting that μxxt + 1 2 10 for any 0 E (0, 1], and thus
dim(Vs.a)
( (reliim
167
(113)
MESpen(M)
t=1
dim(Va.c)
< 161"
Σ
(114)
AESpec(M)
dim(Va.e)
= 167 XESpec(M)
Σ
max {{
Em1
(115)
= =167 f 1i (M))
(116)
where 0 E (0, 1] is chosen so that f E Him (M). Therefore,
ERR(F) R(F*) < 16 2 Wi
vol(M//G)+ + CM/a)
(117)
(2
27

---

+
so²
Wi
(ol(M/G)n
(118)
(2x djn (2r)d
so²
+ (2s - d + 1)n CMIGGT -- 3
(119)
24
+ 1617 I|
11 Him (M) + n²
Il (MM)
(120)
The result is only true when < 00 and 17 2 5R log(n), where R is defined in Equation (98).
We can now optimize the above bound for 1j. First consider the function p(() = c,l + cat on Rz0 for a, b, Cay > O. Note that p(0) = p(x))
and to find its stationary points, we solve pf = 0
and get the only solution t De, ( 1/((+b)) which is thus the global minimum of the function. Thus by minimizing
s
p(n)
16
Wid
vol(M/G))n +
(16]]5*1
H:n (M))
(121)
(2s d)m (2x)a
we get
d
Wi
vol(M/G)) a/(0o+d/2)
(122)
20 11 Hon (m)
d)n (2x)
Therefore, the population risk is bounded as follows:
B[R(F) R(F*)
(123)
16(
Wa (2
vol[M/G)+Cmid vol(M/G) + Cm/a) 0² o² n (2)
Wa Hum (M) (2s d)n (2r)a
d
vol(M/G))
s/(06+d/22)
f+1
011-1-1/00=422))
(124)
8
2
vol(M/G)) -(d-1)/
16
CM/C
(2s
d+
1)n
28
Hit0 (M) (2s- d)n (2
(9n- 100
(125)
32
28(28 d)n (2Th) a vol(M//))
do²
Wd
00/ 00/160+d/2)
|| Ia d/(0otd/2) (M)
(126)
O(n-a=/(o+t//1)
24
f (()))(M))
(127)
n1
0(1/1²)
and this completes the proof since - (x + and the third term dominates the sum.
D Proofs of Theorem 4.6, Proposition 4.5, and Corollary 4.7
Corollary 4.7 follows from Theorem 4.6 on the dimension of the vector space Ho. just according to standard bounds in the literature on the population risk of KRR finite-rank kernels (see [65]). Therefore, we focus on the proof of Theorem 4.6 and Proposition 4.5.
Proof of Proposition 4.5. This is a classical result: one can use variational method to prove it. See [12] for the proof for an arbitrary vector space V. Here, we prove it for V Hg. Consider an arbitrary f = DDP- (f, LE) E Ho. Then, using Equation (27),
E(f.f) = S VV (1)
(128)
28

---

(129)
D-1
$ AD-
Σ
(s, (f
(130)
1=
Ap- -
(131)
and the bound is achieved by f = 0p-1.
Now by Theorem 4.4, the proof of Theorem 4.6 is also complete.
E Proof of Theorem 4.3
In this section, mostly usc/follow standard results in the literature of minimax lower bounds which can be found in [65]. Note that the unit ball in the Sobolev space Hinw((M) is isomorphic to the following ellipsoid (see Appendix A.10):
lay?2 min(1,
E : (a)()))
$1
_ CNN)
(132)
Note that the eigenvalues are distributed according to the bound proved in Theorem 4.4. Consider M functions/sequences fi, f.....: and 8 (to be set later). In other words, let {2,, SAr denote ô o-packing of the set & in the (NN)
: fM E such that I|f f, f 2 6 for all * j. for some M
Consider pair of random variables JJ as follows: first J [M] {1, .., M) and a, M. i i= 1==...... n, are chosen uniformly and independently at random, and then, Z +f) E R", where 6; NNO o²) independent Gaussian variates. Let (-) P(.JJ= = j) denote the conditional law of [Z, J). given the observation J = j. A straighforward computation shows that n DKL(PPp) (a.P = 20 llfe f5ll2 2 né
20 for all i,j E [M].
According to Fano's 's method, one can get the minimax bound
E B[R(A) - R(St) 2 sup
inf f s" EHi [| Il (M)=
(133)
if log(M) 2 J)( + log( Using the
method [65], this condition is satisfied
e² 2 log Nk (c)
(134)
log M 2 4ea + 2 log(2),
(135)
where (E) denotes the e-covering number of the space of distributions P(II.) for some f E & (defined similarly we have [P[[] j) P(-lf fj)), the square-root KL-divergence. However, since DxI. (P)) = fl gllea this equals the coveriing of the space in the (NN (NN)- norm. other words, we have
EO 2 Vi
NKL(E) = Ne((s)
(136)
Now note that, for any M such that log M 2 log Nea (6),, there exists a 8 -packnn of the space in the (2 (see the packing and covering numbers relationship [65]).
In summary, we get the minimax rate of 1 if the following inequalities are satisfied:
(E0V2 /
2 log Nea(N)
(137)
/n
log Ne (8) > 4e 2 2 log(2),
(138)
for some pair 8), Thus, our goal is to obtain tight lower/upper bounds for log Negg (.).
29

---

Lemma E.1. For any positive Ç.
log (N(0)(//2) 2 : log(2)
(139)
log (N (v2)) S Glsd where the quantity ; G) is defined in Theorem 4.4.
O(5 +
(140)
First, let us show how the above lemma concludes the proof of Theorem 4.3. According to the lemma, we just need to check the following inequalities:
2 2 (s/d + log(()) (2rrd vol(M//)
Wd
-d/a + +O(n "n)
(141)
Vn
N((28)- lo) 2 4c + log(2).
(142)
Without loss of generality, let us discard the big-O error terms in the above analysis. In our final adjustment, we can add a constant multiplicative factor to ensure that the bound is asymptotically valid. To get the largest possible 6, we set
2 = (s/d d + log(4)) (2T)
Wa
vol(M//)
GO
(143)
and thus
2= ( + log(4))
(2rrdd
Wa
vol(M/G)) s/(otd/2)
x
0²
-d/(s+d/2)
(144)
Therefore, the following inequality needs to be satisfied:
vol(M//G) 0/(otd/22) 0²
(/+o//222
N((28) = G) log(2) log(4) + 4 ((s/d log(4))
Wd
(2m)a
(145)
Using asymptotic analysis, the inequality holds when
log(2)wa vol(MMGG((2)) d/s 2 4 2 log(4)) (2m))
(2T)d vol(M//G) 2/(x+d/2)
Wa
d/(x+d//2)
(146)
Rearranging the terms shows that
Wi a² vol(M/G) s/(x+d/2)
4
-2s/d
482 <
(147)
(2
log(2) (s/d 2 log(2)) s/(xd//2)
n
==
where C₁ only depends on 2s/d 1. Since this gives minimax lower bound of 50², the proof is complete.
The rest of this section is devoted the proof of Lemma E.I.
Proof of Lemma E.I. Define the following truncated ellipsoid:
E (ao) E :. 2 111 as a==
(148)
where A a parameter defined as
A max max c: No S = Cc:ss
N(
(149)
Note that
5² for ( EE.
To construct covering set, note that according the definition of the truncated ellipsoid, (C) C & ε, where (C( denotes the ball with radius Ç (in 62 (o-morm) is the Euclidean space of dimension A. Using standard bounds in the literature [65]. we get
log Ne (C/2) A log(2).
(150)
30

---

To get the upper bound on the v2ç -255-ovwr covering number, using an argument based on the volume of the
ellipsoid [65], we conclude
Negn (V()) S A Alog(4/()
log(A;")
(151)
2
t=
Algg(4/{)
log(Ae)
(152)
t=
Alog(4/{) 2 2
log(t)dN(t:G))
(153)
"//
dt
llgg(4/)) log(s
2 N(::G)
(154)
2
log((4) + 2 N(t:G) dt
(155)
By Theorem 4.4,
1 G(I:)) dl t I N(C = + *
(156)
2 Wi (2
vol(M/G) d/o + -
(157)
Therefore,
OggNe()) (v2()= s A(s/d log(4)) + 05
(158)
31


Reviews:
[{"review_id": "7HQyMXgTo1", "reviewer": "Reviewer_jgVU", "summary": "This article investigates the sample complexity gained from encoding invariances into learning models. The article focuses on the study of kernel ridge regression on compact manifolds for functions that are invariants to a group action on the manifold. The main result of this article (Theorem 3.1) gives an upper bound of the excess population risk for functions living in the intersection of Sobolev spaces and the set of G-invariant square-integrable functions on the manifold. The analysis shows the importance of two terms: the volume of the quotient space, and the effective dimension of the quotient space. This result quantifies the exact sample complexity gain from invariances for kernel regression on compact manifolds for an arbitrary Lie group action. Moreover, the authors prove that the KRR estimator is minimax optimality. The proofs of the results make use of new results in the field of differential geometry. ", "questions": "-", "limitations": "-", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Although heavily technical, the article is well written and the proven results were extensively discussed. \n- The newly proved results may be beneficial for the community of kernel methods on manifolds. ", "weaknesses": "To be honest, I didn't have enough time to check the proofs thoroughly. Given that the contribution is purely theoretical, I believe it will be better suited for a math-oriented journal, where a rigorous scrutiny of the proofs can be ensured.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the respected reviewer for their helpful comments. Here we provide a response to the questions/weaknesses mentioned by the reviewer.\n\n - Question: \"To be honest ... can be ensured.\"\n \n \n    - Answer: We appreciate the reviewer for mentioning this important comment.  While we cannot put the proofs into the paper (for page limit), we have provided a brief proof sketch in the main body of the paper (Section 3.1), as well as a more detailed proof sketch in Appendix A. We hope that the outline of the proof we provided is useful for the reader.  \n \n \nAlso, many theoretical papers appear in ML venues and we believe that theoretical papers have a place and are useful in the ML community (although this paper is applicable to kernel methods on manifolds, it is also applicable to kernel approximations of neural networks (e.g., in lazy regimes)). We hope that our theory can help better understand the effects of group invariances in the learning problem. \n\n "}, {"review_id": "muWBxIv7cI", "reviewer": "Reviewer_xLSq", "summary": "In this work the authors theoretically study how encoding invariances into models improves sample complexity. They approached the problem from differential geometric viewpoint, rather than common strategy of using invariant polynomials. Since the problem is algorithm and model dependent, the authors considered kernel-based algorithms, as neural networks in certain regimes behave like so. The obtained results generalize and greatly expand previous state-of-the-arts. Hence, the results provide a reduction in sample complexity that was not possible with previous assumptions. The paper also shows how these results transfer to popular invariant models, such as DeepSets, GNNs, PointNet, and SignNet.", "questions": "- None", "limitations": "- Theoretically intense, so for some readers, might be hard to follow.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper discuss one of the major challenges in machine learning, i.e., sample complexity.\n- This work provides theoretical results on how incorporating invariance in model can improve sample complexity. Their results are more general and can achieve better bound.\n- Well written.", "weaknesses": "- None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We thank the respected reviewer for their positive review and appreciation of the theoretical results. For the next version, we will pass the paper and make it more readable to address the issue mentioned in the limitations section. Indeed, we are planning to add figures to the paper to make the problem and contributions more visible. \n \n \n "}, {"review_id": "7oPspkzybA", "reviewer": "Reviewer_doFr", "summary": "The paper analyzes the generalization error of kernel ridge regression on manifolds with a kernel invariant to a group action. Compared with previous work, the results hold more generally for groups of positive dimension.\n", "questions": "No question", "limitations": "No limitation identified.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles an important issue, is well-written, with well-chosen and appropriate examples, and appears technically sound. It also offers a differential geometric perspective on learning theoretic issues which might have its own interest. \n", "weaknesses": "Though already significant in its present form, the paper would gain in interest if it could provide more \"agnostic\" generalization error bounds in various ways, or at least comment on how (and if) this would be possible.\n\n- Assumptions on f*: While interesting per se, the results are inapplicable to practical cases without knowledge of the target function f* (and the noise level sigma^2). In particular, Theorem 3.1 makes strong assumptions on the target function f* and holds only for the optimal value of the regularization parameter. It would be much stronger if it could be reformulated to hold more broadly for all regularization parameters with, e.g., the norm of \\hat{f} instead of that of f*, and with f* only involved through the empirical risk (like more \"traditional\" error bounds based for instance on the Rademacher complexity).\nIn other words, if invariance to a (finite) group G intuitively implies that \"each data point is worth |G| data points\", does it also imply something like \"the complexity of a model class taking into account the invariance is the standard complexity of the model class divided by (the square-root of) |G|\" (where the complexity can refer for instance to the Rademacher complexity)? \n\n- Assumptions on G: the results depend on knowledge of the group G. What if G is only approximately known? For instance, what if the kernel K is invariant to G' while f* is invariant to G with G' slightly different from G (or if G' contains only a subset of the transformations in G)?\n\n- How much of the result relies on the uniform distribution of x on the manifold? Could you comment on what terms would be affected by a change of measure in Theorem 3.1 and if the gain as G grows remains of the same order in this case?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the respected reviewer for their helpful comments. Here we provide a response to the questions/weaknesses mentioned by the reviewer.\n\n\n\n- Question: \"Assumptions on f*\"\n\n    - Answer: We thank the reviewer for mentioning this important comment. Indeed, the KRR algorithm does not need any information about the function $f^\\star$ rather than its Hilbert space norm $|| f^\\star ||_{\\mathcal{H}}$ (just to determine the regularization parameter). However, according to Equation (120) in the appendix, we only need an upper bound on the Hilbert space norm of the function $f^\\star$ (which is a common assumption while studying kernels). The upper bound will let us compute the regularization parameter and run the algorithm without any further knowledge of the target function, and also Theorem 3.1 is still valid if one replaces the upper bound on the Hilbert space norm of the target function instead of its true value (same is true for the noise variance). We note that having an upper bound on the Hilbert space norm is essential to prove an upper bound on the population risk because the Hilbert space norm, intuitively, characterizes the \"complexity\" of the class of function to be learned. We thank the reviewer for mentioning this important aspect of the result and will add a detailed explanation in the next version of the paper. \n\n    Also, for scaling the complexity of the model class under invariances, we believe that the complexity will reduce as the reviewer correctly mentioned, but the exact scaling highly depends on the notion of the complexity used in the problem. We believe our dimension counting formula could be used as a  way to compactly quantify this complexity, and have potential applications to future works. \n\n\n\n- Question: \"Assumptions on G\"\n\n    - Answer: Since the results in the paper hold generally for arbitrary Lie groups, if one only knows the invariances according to a smaller group $G'$ then the upper bound is still valid and is reduced to the one with $G'$ replaced instead of $G$.  We will add explanations about this to the next version of the paper. \n\n\n- Question: \"How much ...\"\n\n    - Answer: Thanks for mentioning this comment. We cannot expect the gain to be true for \"any\" distribution. For example, think of a distribution supported on only a submanifold of the original manifold, then the problem is effectively learning on a smaller manifold and all the volume/dimensions must be corrected accordingly. However, if the sampling distribution has full support, with an upper bound or lower bound on its density (compared to the uniform distribution), then the same rate is achievable within constant factors. Since the main goal of this paper was to quantify the gain of \"invariance\" we just focused on the uniform sampling for simplicity while it's not restrictive. We will add these explanations to the paper in the next version. it's\n\n\n"}, {"review_id": "x3py3dHWrY", "reviewer": "Reviewer_DGX1", "summary": "This paper analyzes the impact on sample complexity of encoding invariances into kernel functions in the context of kernel ridge regression. A kernel function is invariant to the actions of a group if its output does not change when its inputs are acted on by members of the group. The paper shows that for finite groups, the sample efficiency is effectively multiplied by the size of the group. For groups of positive dimension, it shows the sample efficiency is improved by (1) reducing the effective dimension of the input manifold, and (2) reducing the volume of the manifold.\n", "questions": "See the weaknesses section.", "limitations": "Perhaps a broader discussion of limitations would be useful.\n- What deep learning scenarios would the results from this paper apply to or not apply to?\n- What important open problems remain to be solved?\n- How empirically predictive are these theoretical results, in different settings? In what cases would these results definitely not be empirically predictive?\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Significance: This paper analyzes how invariance improves sample complexity for kernel ridge regression in a much more general setting than prior work. For example, it allows the input space to be any compact manifold, and the invariance to be represented by any smooth compact Lie group (prior work, for example [5], had assumed the input manifold was a sphere and that the invariance was to a finite group).\n- Quality: Although I have not checked the proofs, the quality of the work appears high. The generalization bound in Theorem 3.1 is proved to be minimax optimal in Theorem 3.3, an interesting/important result.\n- Clarity: The paper is generally well written and clear. See “Weaknesses” section for places for improvement.\n- Originality:  It seems the approach of using differential geometry to analyze these generalization bounds is original, and that the authors developed some tools of independent interest in this area.\n\nOverall, I believe this paper makes an important theoretical contribution to a problem space that has been of significant interest to the machine learning community: namely, how to make models invariant to certain input transformation (either via data augmentation, or by changing model architecture), and understanding how encoding these invariances impacts the models’ generalization performance and sample complexity.\n", "weaknesses": "Perhaps the greatest weakness of this paper is at times seeming too “mathy” (https://arxiv.org/pdf/1807.03341.pdf), without sufficient grounding in concrete examples or empirical results. For example:\n- It would have been useful to go over more examples of invariances whose groups have positive dimension, and understand more concretely how these invariances affect the generalization bound.\n- It could be useful, for equations (5) and (7), to give examples of how this quantity changes for different finite vs. infinite (positive dimension) groups. One example I had in mind, for $x \\in R^2$, was rotational invariance, where the rotations could be in a finite group (e.g., rotate by multiples of $\\alpha$ degrees, for any $\\alpha$ that evenly divides 360) or an infinite group (e.g., rotate by $\\beta$ degrees for any real-value $\\beta \\in [0, 360)$). How would these situations compare, in terms of equations (5) and (7), as the value of $\\alpha$ approaches 0?\n- It would have been helpful to understand which of the examples given would not have been possible to analyze with prior results.\n- It would have been useful to run experiments (even toy/synthetic experiments if necessary) to demonstrate that the bounds from the paper are actually predictive of model performance.\n\nNIT: $\\omega_d$ is defined in Theorem 3.4, but used in prior theorems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n We thank the respected reviewer for their helpful comments. Here we provide a response to the questions/weaknesses mentioned by the reviewer.\n\n\n- Question: \"It would ... generalization bound.\"\n  \n  - Answer: We thank the reviewer for their comment. While we devoted a full section to examples and applications (Section 4 in the main body of the paper), we appreciate the reviewer's suggestion and as there are many examples of learning under invariances (e.g., in physics) with different groups, we will survey even more in our next version to clarify the various kinds of gains available according to our results. \n  \n - Question: \"It could ... approaches 0?\"\n  \n  \n     - Answer: We will add the example provided by the reviewer to the paper and add more explanations since it allows easy computation of the gain and makes the paper more readable.  Indeed, since we are going to approximate a one-dimensional group using finite groups, the gain is in the exponent and thus the one-dimensional group is always better (for large sample sizes).\n  \n  \n  - Question: \"It would ... prior results.\"\n  \n      - Answer: Since all the provided examples are not using spheres, they are not possible to be analyzed using the prior work. We will clarify this in the next version of the paper.\n  \n  \n  - Question: \"It would ... model performance.\"\n  \n      - Answer: Thanks for making this suggestion. Although we believe that the results are theoretical in nature, we plan to add supporting experiments to the next version of the paper.\n   \n  \n  - Question: \"NIT ... theorems\"\n  \n      - Answer: We will clarify it in the next version of the paper. \n\n - Question: \"What deep learning ... to?\"\n \n     - Answer: The results apply to the kernel approximations of deep networks (e.g., lazy regimes), but for general deep learning it's still an open problem. We will clarify this in the paper. \n \n - Question: \"What important open problems remain to be solved?\"\n \n     - Answer: Perhaps the main open problem is to generalize the results of the paper to sample the complexity of other statistical estimation problems  (e.g., Wasserstein distance, density estimation, etc.) under invariances on manifolds. Also, it's interesting to exploit the possibility of applying the results to NTK regime for invariant models. We will add this to the paper. \n \n - Question: \"How ...  predictive?\"\n \n     - Answer: We believe that the gain is observable almost everywhere in practice, but the quality of the approximation fairly depends on how the assumptions on the paper are satisfied in practice. We will add more explanations about this limitation to the paper. \n \n \n"}]

Author rebuttal:

Meta-review: The submission is about understanding the gain achievable when learning with invariances under the umbrella of reproducing kernel Hilbert spaces. More particularly, the authors focus on kernel ridge regression (2) on smooth connected compact Riemannian manifolds, where the target function is invariant w.r.t. compact Lie group actions. Using differential geometric tools, they establish minimax optimal (Theorem 3.3) and achievable (Theorem 3.1) excess risk bounds in this setting which show the gain terms of the reduction of the volume of the manifold and that of the effective dimension. The theoretical insights are followed by examples of learning scenarios with commonly-deployed invariances.

Kernel methods are among the most powerful tools of our times. The submission is clearly structured and well-written. The reviewers agreed on the novelty and importance of the theoretical results established in the manuscript. The paper is of definite interest to the NeurIPS community.
Decision: Accept (spotlight)