On the Sample Complexity of Learning under Geometric Stability
Authors: Alberto Bietti
Luca Venturi
Joan Bruna
Venue: NeurIPS 2021 Poster (2021)
Keywords: invariance
learning theory
approximation
kernels

Abstract: Many supervised learning problems involve high-dimensional data such as images, text, or graphs. In order to make efficient use of data, it is often useful to leverage certain geometric priors in the problem at hand, such as invariance to translations, permutation subgroups, or stability to small deformations. We study the sample complexity of learning problems where the target function presents such invariance and stability properties, by considering spherical harmonic decompositions of such functions on the sphere. We provide non-parametric rates of convergence for kernel methods, and show improvements in sample complexity by a factor equal to the size of the group when using an invariant kernel over the group, compared to the corresponding non-invariant kernel. These improvements are valid when the sample size is large enough, with an asymptotic behavior that depends on spectral properties of the group. Finally, these gains are extended beyond invariance groups to also cover geometric stability to small deformations, modeled here as subsets (not necessarily subgroups) of permutations. 

On the Sample Complexity of Learning under Invariance and Geometric Stability
Alberto Bietti NYU
Luea Venturi NYUł 1v8008nyu.ed edu
Joan Bruna NYU
alberto. alberto.biettinnn wwettiiiit.......
brunaâcims nyu. nyu edu
Abstract
Many supervised learning problems involve high-dimensional data such as images, text, graphs. In order make efficient of data, it is often useful to leverage certain geometric priors in the problem at hand, such as invariance to translations, permutation subgroups, or stability small deformations. We study the sample complexity of learning problems where the target function presents such invariance and stability properties, by considering spherical harmonic decompositions of such functions on the sphere. We provide non con-parametric rates of convergence for kernel methods, and show improvements in sample complexity by factor equal the size of the group when using an invariant kernel over the group, compared to the corresponding non-invariant kernel. These improvements are valid when the sample size is large enough, with an asymptotic behavior that depends spectral properties of the group. Finally, these gains are extended beyond invariance groups to also cover geometric stability to small deformations, modeled here as subsets (not necessarily subgroups) permutations.
1 Introduction
Learning from high-dimensional data is known to be statistically intractable without strong assump- tions on the problem. A canonical example learning Lipschitz functions, which generally requires number of samples exponential in the dimension due to the curse of dimensionality (e.g.. (31).. Many high-dimensional machine learning problems involve highly structured data such images, text, or graphs, and may exhibit invariance to certain transformations of the input data, such as permutations, translations or rotations, and near invariance to small deformations. More precisely, if A' is the high-dimensional data domain, and G is set of transformations a X > X', the learning task can be alleviated one knows advance that the target function f varies smoothly under transformations in G: (f(o I)) f(x)] is uniformly small over Z E X' for a E G.
To further motivate this property, is useful view the data domain X' a space of signals X'= = (2; R) defined over a geometric domain Ω, such as 2d grid. The set of transformations G can then articulated in terms of Ω rather than X, much simpler geometric object, and then lifted into X' by composition: if a Ω + Q and æ E X' then (a (u) == z(α I for every Ω2 The smoothness transformations can thus be interpreted
form geometric stability.
In this paper, we quantify the sample complexity gains brought by geometric stability. Concretely, consider target functions ff defined on the sphere X' gd-1 in d dimensions with finite I (Sd norm. this case, we view the geometric domain as the discrete grid Ω = [1..... d]. and consider geometric transformations G as subsets of the symmetric group of permutations of
"Center for Data Science, New York University.
Courrnt Institute for Mathematical Sciences, New York University. CCenter for Data Science and Courant Institute for Mathematical Sciences, New York University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

elements. Given a set G (not necessarily group), we consider the smoothing operator given by Saf(z) क Eoec f(o z) for f L2 and assume that our target function f is geometrically stable, in the sense that f = Sag for some 9 L2(8"=1). In words, the smoothing operator Sç replaces the prediction f(a) by the average over transformations z. In particular, functions which are invariant under the action of G. namely
flo x)- f(x), ae G, gd-1
are also stable, with / f Saf.
Building on the recent work [23). we proceed by studying harmonic decompositions of such functions using spherical harmonics [14]. which generalize Fourier series on the circle to higher dimensions. This allows us to obtain rates of approximation for invariant and geometrically stable functions with varying levels of smoothness, and to study the generalization properties of invariant kernel methods using kernels defined on the sphere. Specifically, our main contributions are:
By comparing spectral properties of usual kernels on the sphere with invariant ones, we find that the latter provide improvements in sample complexity by factor of the order of the size of the group when the sample size is large enough (Section
We study how this improvement factor varies with sample size, terms of the structure of the group and spectral properties of the permutation matrices it contains (Section 4
We extend the invariance analysis to geometrically stable functions, establishing similar gains in sample complexity that depend on the size of the transformation subset (Section 5
Our proofs rely on comparing the dimension of invariant and non-invariant spherical harmonics at a given degree, and showing that their ratio decays to the inverse group size as the degree tends to infinity. contrast to [23], we consider the dimension be fixed and study non-paranne non-parametric rates of convergence for potentially non-smooth target functions and general groups of permutations, while they consider a different regime in high dimension and focus on invariance to translation groups.
Related work. Invariance and deformation stability have been analysed using convolutional neural network-type architectures such the scattering transform 22
convolutional kernels 66 20 While these works characterise the stability in terms of the dyadic structure of convolutional filters (such as wavelets), they do not cover statistical analysis of sample complexity. Similarly, models of compositional functions such as those in 11 [4]] 27 study the benefit of hierarchical representations with local connectivity for approximation, while [99 21 study benefits of local connectivity with optimization-basee
algorithms; yet these works do not consider invariance or stability. (23] studies similar benefits of invariance but in a different, high-dimensional, regime where only polynomials can be learned, focusing on translation groups, while we consider arbitrary groups or sets of permutations in fixed dimension. [5] also sudies benefits of group invariance, but focuses on linear models, and only considers interpolating estimators. [00 study general generalization bounds of invariant classifiers that scale exponentially with the dimension, which would be pessimistic under our assumptions. [10) study benefits of equivariant kernels in structured prediction problems. 13 studies generalisation advantages of CNNs over fully-connected models, while our focus is on non-parametrics.
2 Preliminaries
In this section, we describe our setup and provide some background on harmonic decompositions on the sphere, and how these are affected by invariance.
Statistical learning setup. We consider supervised learning problem where the data distribution p on input-label pairs (z, y) is such that x E Sd-1 and BØy[=] = f (x) for some target func- tion f' (I For simplicity, we will assume that :r is uniformly distributed on the sphere, and denote the uniform measure on gd-1 by dr. We consider regression setup with La risk given by
R(}) E(z,)>=p [(((x) y
For a given estimator fn based on n samples from p. the goal is then to obtain generalization bounds function of n on the excess risk
B(R(f.)] R(f*) ElIf (
(2)

---

where the expectation is over the n samples, Such bounds are well-studied for various classes of target functions f such as smoothness classes, and estimators such as kernel ridge regression. These are typically studied through harmonic decompositions of ʃ* and of kemnl function in appropriate 1,2 bases, which then relate function regularity and decays of Fourier coefficients.
Harmonic analysis on the sphere. When considering functions in (dT an appropriate choice of orthonormal basis that of spherical harmonic polynomials [ 14 More precisely, de- note (Yx,, 1==1 (d.k) denote an orthonormal basis of the space Va, of spherical harmonics of degree k, i.e., homogeneous harmonic polynomials degree k, where (d, k) = 2k+d-2 (kttd=)) Then, the collection {YR.g k 2 0.j = -...., (d,, k)} forms an orthonormal basis of L [dT),, so that any function f E (dT) may be written
d-2
N(d.) Σ
(
Σ A20
aR
(ey(,r)
with >x 2j=1 Ee < 00. Similarly, any dot-product kernel K (xx,x') x((x,x))) on the sphere may be written
(d.k)
N(d.R)
x((x,x))) Σ MR Σ
(z.,
(4)
1=1
Here, wp-1 is the surface measure of the sphere in p dimensions, and Pa. are Legendre or Gegenbauer polynomials of degree k in d dimensions (normalized with (1. = 1),hhich form orthogonal basis of (²- 1], dw), with dt)(t) (1 (d)(22) dt. When the kemnl K is positive definite and is used in the context of kernel ridge regression with data uniformly distributed on the sphere, then the μi also correspond to the cigenvalues of the covariance operator. These eigenvalues and their decay then control the statistical properties the kernel ridge regression estimator g
where μ4 is given by p4 Ma-2 [ k (())
wy-1
Spherical harmonics and group-invariant functions. In order to describe harmonic decomposi- tions of functions satisfying the group invariance property ① for a discrete group G, we follow 23 and define the symmetrization operator
Saf(x) = G
Σ f(a.x). OEG
(5)
This operator acts as a projection from (dr) to subset thereof which contains invariant functions. It can be shown that the spaces Vd. of spherical harmonics of degree k are stable by SG [23] and we may then define an orthonormal basis of VaN := VaVa, consisting of invariant spherical
harmonics (Y j=1
N(d,k) We then have the following lemma.
Lemma (Representation of projection
23
For any k 2 have
N(d. k)
(k(k)
Σ OEG
E2 (Pa,((0 x, x))]
(6)
N(d,k) k)
G
The quantity ya(k) will play an important role in determining the gains in sample complexity brought by invariance. We will show in Section 4| (k) converges to 1/IG for large k. with asymptotic behavior that is governed by spectral properties of the elements of the group.
3 Sample Complexity of Invariant Kernels
We begin our study by focusing on the invariant case. In this section, we study the sample complexity of learning invariant functions, by considering kernel ridge regression estimators and providing non- parametric rates of convergence that illustrate the gains achievable with invariant kernels compared to non-invariant ones.
3

---

Kernel ridge regression (KRR) and invariant kernels. RKHS Hg. we consider the KRR estimator fA given by
For a positive definite kernel K with
fa = arg min JEHX
(f(x.)) - 11)2 + 1ll
(7)
We consider the following kernels, which assume positive definite, given for x' E @gd- by x') = (((2,2')))
Ko(xxx²) = |G
Σ BEG
k((a x, 2,2")),
(8)
with x(u) < 1. A common example for x is the arc-cosine kernel
[9, which arises from infinite-wide wiith shallow neural networks with ReLU activations. The following integral operator defined on (ddr and its eigen decomposition play an important role for the statistical and approximation properties of kernel methods:
Tx](x)) = f K(x, ((x")))((
We now show that its spectral properties are closely related for K and KG.
Lemma 2 (Spectral properties of K and KG.). There exists a basis of spherical harmonics in which the operators Tk and Ta are jointly diagonalized. They admit the same eigenvalues μlg in (4). with multiplicity (d, k) for Tk and N [d, k) for Tka-
The decay of the eigenvalues μa controls the smoothness of functions in the RKHS, for instance when μ* decays polynomially. Tx behaves similarly to powers of the Laplacian on the sphere, leading to functional spaces similar to Sobolev spaces. For the example of the are-cosine kernel, μág decays
as h -d-2 leading to an RKHS containing functions with d/2 + bounded derivatives 2
Approximation error. The approximation error of kernel methods is often controlled by the following quantity (e.g.,
[2)::
An(A, f*) = inf |lf - f + Allf
(10)
FEH
where f is target function in (dr). and H is given RKHS. In particular, f is smooth enough while if f H. e.g., if f is only Lipschitz,
so that f E H. then we have (A, S then (A, f*) typically grows much faster with A. We now show a useful result for invariant targets,
ff
showing that in this case the approximation error is the same for the kernels K and Kg-
Lemma 3 (Approximation error for invariant functions.). If f is invariant to the group G, so that f Saf"" then we have
Ahx (x, = AzCoO (*,
(11)
Degrees of freedom. The above result suggests that any gains of using Kg instead of K for learning invariant functions should come from estimation rather than approximation error. The estimation error of ridge rigression estimators is typically controlled with the following quantity, often called degrees of freedom or effective dimension (e.g., 18)::
Nx Tr(Ex \
Σ m=0
Am
(12)
Am +
where ΣK = Egg [K(x,)) 0Hx K(x, )] is the covariance operator and (Am (Am)m20 its eigenvalues, taking multiplicity into account, which are the same as those of TK when data is distributed according to dr (8). We then obtain the following simple result relating NKc to No..
Lemma 4 (Degrees of freedom for K and Ka.). For any E 2 O, we have
NKc (A) S (() + (x())Nx(A)) where = Exee (dd,k) and (C) sup (k), with Ya given in (6)
This suggests that for fixed E, the effective dimension of KG is controlled by factor va(() times that of K, up to a finite fixed dimension ((e). For difficult non-parametric problems which require small À at large sample sizes, the second term will tend to dominate, so that having small va(() may help reduce sample complexity compared to using the vanilla kernel K, an observation which we make rigorous below.

---

Generalization bound for KRR. Armed with the above lemmas on approximation error and degrees of freedom, we now study generalization of KRR under the following assumptions:
(A1) capacity condition: (A(()) S CRA -1/a with 1.
(A2) source condition: there exists r that f T
a-1 and E (dT) with l19llez(ar) S Cy. such
2a
(A3) invariance: f is G-invariant.
(A4) problem noise: is such that F S oz.
The first, second, and fourth conditions are commonly used in the kernel methods literature 8 (A1) characterizes the "size" of the RKHS, and is satisfied when the eigenvalues Am of TK decay as k- On the sphere, a 2e_ corresponds having s bounded derivatives, e.g. we have the arc-cosine kernel. The parameter in (A2) defines the regularity of f" relative to that of the kernel: r = 1/2 corresponds to /" E HK. while larger (resp. smaller) r implies ʃ is more (resp. less) smooth. The condition on is needed for our specific bound, which is based on 3 Proposition 7.2), We now present our bound on
d/2 + 1 for
but may be bypassed using different algorithms or analyses 17 26 the excess risk.
Theorem 5 (Generalization of invariant kernel)., Assume (AI-4). Let va(L) be as in Lemma or upper bound thereof, and assume Vy == infe2o val() >
Let n 2 max [1l/ (C1/vg) zarii=a j. and define
in suple D(E) S C2va(() 20r47 Sorrrnnnaa 2 We then have, for (L.) (n)o))/
(13)
vv((e)) n2
2ar ZOF4T
B[R(AA) R(f") Co
(14)
In the same setting, KRR with kernel K and X = Czn achieves E(R((A)-R( S Can 2ort1 where C3, C1 are the same constants as for the invariant kernel. Here, the constants C1 only depend on the parameters of assumptions (A1-4).
The theorem shows that the generalization eπror for the invariant kernel behaves as if it effectively had access to n (f,) samples, so that va(en) plays the role of an effective inverse sample complexity gain at sample size n. Note that (fx) < 1 and Va is decreasing, so that we always have some improvement in sample complexity, and this gets better when l, is large. particular, we show in Section 4 that yaa (k),,, and hence va(E) converge to I/|G", so that asymptotically the gain in sample complexity can be as large as the size of the group, which in some cases may grow exponentially d.
Asymptotic estimates of the effective gain ve((x)) We now study the asymptotic behavior of the effective gain factor va(en) when n - 00, by considering case where an asymptotic equivalent of (f( in l is known:
va(l) 40 + -
In Section we obtain such asymptotics with v0 = 1/IG], and a rate 3 that depends on spectral properties of the elements of G. well upper bounds with possibly faster rates 3 at the cost of larger un- In Appendix B.5, we show that we may leverage this to obtain the following asymptotic estimate of the effective gain (fx))
va(en) S Vo + min ( (a (1 na
(15)
Notice that when 3 < d, both exponents of display curse of dimensionality, but this curse goes away as grows. Note also that the first exponent yields faster rate, one that only achieved for large n due to the factor 2ar, which may be small for large groups.
Curse of dimensionality and optimality. Note that the bound obtained Theorem 5 still cursed for an invariant target f", in the sense that the exponent in the rate is of order 1/d when I" is only assumed to be Lipschitz. Indeed, Lipschitz assumption on I" corresponds to taking and a such that 2ar 2/(d- - 1), which makes the source condition (A2) similar to bound on V [())))))))
5

---

This then leads to a cursed rate 2/(22d-1), raising the question of whether this can be improved. We note that since (k) = (1 (as we show in Section 4). the asymptotic decays (as function of k) of the coefficients of I and of the eigenvalues of Tke are similar to those for the non-invariant case, which implies that these rates cannot be improved (see, e.g., (.) In Appendix B.6, we show that our bounds with an improvement in sample complexity by factor |G] are asymptotically minimax optimal, so that this may be the best we can hope for under our assumptions.
Comparison to [23] The work [23] also consider non- con-paraettric learning of invariant functions with similar kernels. They consider a high-dimensional regime where + oo with sample sizes in polynomial scalings = d" for some s. They then show that if (k)) = Oa(d-a) as d + co, for some a > 0 (which they call degeneracy), then the invariant kernel can learn polynomials of degree & with n s d==a while the non-invariant kernel needs R d' samples. In some cases, such as the cyclic group, [3 show a = and hence the gain of factor d = d equal the size of the group, but in other cases d" may be smaller than the group size. For groups of size exponential in d. the analysis in [23] may only achieve polynomial improvements by factors d", in contrast to our analysis, which considers the different regime of fixed d and n oo, and may lead to gains by exponential factors if [G] is large, at least asymptotically.
Counting Invariant Polynomials
In this section, we study the asymptotic behavior of >a(k), given in (6). when k -> xo and the dimension d and the group G are fixed. This quantity can be seen as capturing the fraction of orthogonal spherical harmonics of degree k that are invariant to G, and helps us control the possible gains in sample complexity for learning invariant functions,
described in Section 3 Denoting Yd.o (k) := E. [Pa, Iz x))]. we will show that % (k) vanishes for large k for any that is not the identity. This implies that 7a(k) converges 1/|G], since we trivially
have (k) = Pa.*
1. We further characterize the asymptotic behavior of ya(k) in terms of
properties of the group elements. In the following we consider the case of G being a subgroup of Sa.
the groups of permutations on d elements.
Decay of Yd.o (k)). Our main insight is to leverage the fact that when is not the identity, then the random variable 2, = (o- z)) when æ ~ 7 admits a density on [-1, 1]. which we denote qa. This by itself will prove sufficient show that 7d.- (k) decays for large k. thanks to the oscillatory behavior of Pa,A. We can then further characterize its asymptotic behavior by studying the singularities of fo. leveraging the seminal work of Saldanha and Tomei (28]. In particular, these depend on spectral properties of the matrix associated to a.. We summarize this in the next proposition.
Proposition 6 (Asymptotic behavior of Tá,o Let Ag be the matrix associated to + Id. that is such that a x = AGR. Denote by Ag the set of (complex) eigenvalues of An, and by mx the multi- plicity of X E Aa- When k DG, we have the asymptotic equivalent Ta, ExEr, (kk), where
-d-mm + o(k-d+ma), k d+ + o(k -t--mt))))
(k)) <
(16)
otherwise,
where E hides constants that may depend on d, a and X.
Every permutation E Sa (where Sa is the symmetric group of permutations) can be decomposed into cycles on disjoint orbits; the eigenvalues À (and their multiplicities m,) of a matrix A, admit an interpretation based on such decomposition. Indeed, since A, is unitary, its eigenvalues are of the form = 2 and one can verify that necessarily 0 = + E Q. Furthermore, assuming w.l.o.g. that is prime, such eigenvalue appears whenever a contains a cycle of length a multiple of g. In particular, the multiplicity of the cigenvalue 1, m1, corresponds to the total number of cycles in such a decomposition, which we will denote by c(a). Then Td.- can be controlled as follows.
Corollary 7 (Decay of na (k)). Let a + Id, and let c(a) denote the number of cycles in a. Then,
k (k-())
if((o)
d+3
Td.o (k) S 1 4/246
2
otherwise.

---

Decay on specific subgroups. We may now use Corollary 7 to study the asymptotic behaviour of Ta(k) as l so for various choices of subgroups of Sa, using the following result.
Corollary 8 (Upper bounds with permutation statistics). Let G be a subset of Sa and define <(G, Ho E G c(o) sor 8 [d 1|. Then, for any have
0N ((G,s) +0 (K-dtmau f--dtmxxss, 4/2+6))
Ta(k) -
(17)
G|
with equality if is such that ((G,s) 8) 1.
Note that such an upper bound immediately yields similar upper bound for va(() as defined in Section which then controls the effective gain in sample complexity in Theorem Indeed, (17)
implies that there is constant C' such that for all k > Ta(k) S ((G,s)/ + d+ d (,.4/268) Since this upper bound decreases with k, we obtain
vo(E)= S S(G,s) + CE (CE-dtmax(x.d2240 |G|
In the context of the generalization bound of Theorem 5 and our heuristic derivation thereafter, the effective gain in sample complexity is then governed an upper bound on va(en) ) as in (15). with asymptotic gain Ba ((G.s) and rate B d - max(s, d/2 6}.
|G]
Example 9 (Translations). Let G = Ca be the cyclic group d elements. Then it holds
1 d + (k-4/2+6))
Ta(k) This follows by noticing that every translation a (but the identity) satisfies c(or S. d/2. This leads to an asymptotic gain Vo = and 3 = d/2 - 6 leads to fast convergence in (15) even when is large. Example 10 (Local translations). Let d = 8 r (with r, 8 2 foror simplicity), and consider the group composed of traslations over blocks of coordinates of size 8; i.e., the block-cyclic group
G= fo o= ==)(2) o o... o.())
where each (00) is translation over the set { 1)8 + 1....,,,)) is), E [r]. Then it holds
[k(kk) = 8 + + (K- (K-
(18)
This follows by noticing that every local translation (but the identity) satisfies c(a) S (d- 8) + +s/ s/2. Here the asymptotic gain is vo s" sd//s, which can be exponential in when is small. We have B = 8/2 1, which leads to much slower convergence than the translation case, unless is large and of order d.
Example 11 (Full permutation group). For the case of SS, we can split the group based on the value of Fix(a), the number of elements fixed by permulation a. Denote
( (dd
d Σ
(G E Fix(o) > s/
j=s+1
for s E [d - 1). where !K denotes the k-th subfactorial. Then we have
Ta(k) < {{G,s)
d! + O -I:::d/ttmaxe 4/2+ 6)
with equality for s d 1. This follows from the fact that c(a) S Fix(o) + (d (dxxix()))/2 In particular, it follows
2
na(k) (s 1)!
+ +0
When considering the full group, we may get a large asymptotic improvement of order vū - G| d! in sample complexity, but slow convergence with 8 - as per Corollary & (assuming d large enough). Using different values of muy yield different upper bounds with faster convergence rates 8 d/2 max max(s/2, 2), but smaller asymptotic gains sample complexity, given by vi (s 1)1/2. For instance, with s = d/2 and d large enough, we have B = d/4, leading to potentially fast convergence rate in 75 towards a sample complexity gain that is still significantly large, of order (d/2 + 1)!/2.
Overall, these examples show that the size of the group determines the best possible improvement in sample complexity, while the spectral properties of its permutations dictate how quickly we may achieve these gains.
7

---

Beyond Group Invariance: Geometric Stability
In this section, we study gains in sample complexity when the target function f is not fully invariant to group, but may be stable under small geometric changes on the input. We formalize this by considering a similar averaging operator Sc. but we allow G to be a generic set of permutations instead of group, and allow for weighted average:
Scf(z) == Σ h(o)f(o x),
(19)
TEG
where h(o) 2 for all a E G and Exech(o) when E G and h) h(o), so that SG is self-adjoint. In this case, images of Se are not invariant functions, but may nevertheless exhibit a form of "local" stability to small perturbations of the input data. For instance, if G consists of local translations by at most few pixels, or if' G consists of all translations but h is localized around the identity, then applying Sg yields functions that are stable to local translations. We may also consider more structured set G of permutations that resemble local deformations, consisting of both a global translation as well as different local translations different scales, we describe below.
We assume that G' is "symmetric", i.e., o E G
Spectral properties of Sc. Note that in this setup, we longer have that SG is a projection, however we may still view it as a smoothing operator, which attenuates certain harmonics that are "less" invariant than others. The next lemma shows related spectral properties to the invariant case.
Lemma 12 (Spectral properties of Sc). There exists a basis of spherical harmonics Y k. for 2 and 1...., N (dd, k), in which the operator SG is diagonal, with eigenvalues XR.j 2 0. In analogy to Lemma 7 we have
(d).))
ra(k) = Nd,,))
Σ
Σ oEG
((o)) (2,2))
(20)
We also define va(e)= == supkze (k))..
Sample complexity of stable kernel. In analogy to Section we may consider a stable kernel
Kala, 2') = Σ (M xI,")).
(21)
OEG
Then, it is easy check that the integral operator of KG is given by TKe TGT In contrast to Section 3 we no longer have that the approximation errors of K and KG are the same in general on "geometrically stable" functions, since the notion is not precisely defined. Nevertheless, represent favorable targets /* as those whose coefficients decay similarly at each frequency k to those of Sa. by viewing it as a smoothing of some 2 function g² i.e., With this in mind, we make the following assumptions, replacing assumptions (A1-3) of Section 3
may
S7 for some exponent r.
(A5) capacity: the eigenvalues (Sm)me m20 of Tk satisfy Em S (0m++1)-
(A6) source condition: there exists that f = Kg..
a-1 and g E (ddd with l|all>>(ar) S Cy. such
Note that (A6) corresponds to standard source condition with the kernel KG (since 77 SGTR). yet it reveals how KG jointly performs smoothing on the sphere, through Tk, as well as on permutations through Sç. While these two forms of smoothing appear "ppear"ennanglen "entangled"" in this assumption, one may balance them by choosing different levels of smoothing in the kernel function K, or by averaging multiple times in (2T). Assumption (A5) needed for obtaining variant of Lemma and implies (Al) with Ck /aaa, We then obtain the following generalization bound.
Theorem 13 (Generalization with geometric stability.). Assume (A4-6), and assume vo
inf (e) > 0. Let n 2 m /2, (Ci/vo) 1/2ar++--a)))) and define
f, = sup(e: D(E) S Czva(e) 20)t2))))ttmmtttt
(22)
8

---

We then have, for À Cs(va(Ln)) /nmna///tt/t)tttt)))))
R(F*) Ca (uulln))aa
Inr-T
(23)
In the same setting, KRR with kernel K achieves similar bound with va(en) / replaced by 1, but with a possibly smaller constant Ca. Here, the constants CLa only depend on the parameters of assumptions (A4-6).
Note that the obtained generalization bound very similar Theorem but with a factor val ( 1/o instead of va(f.). This is due to the fact that in contrast to the invariant case, where (a(k) in (6) can help precisely control the number of invariant spherical harmonics, in this case Ta(k) as computed in (20) can only give information about the sum of the eigenvalues ÄR.j at frequency k, which may be insufficient to precisely estimate the gains in effective dimension. The gap between these two factors is relatively small for kernels with slow decays (a 1) but can be more pronounced for smooth kernels with fast decays (large a:). Note also that the different source condition (A6) leads to different approximation error, and thus to approximation -estimattoot trade-off related to stability, which does not appear in the group-invariane case. More precise estimates of the decays of A may help characterize this tradeoff more formally, and we leave this question to future work. As (5) we may derive an estimate of va(f)), namely (f( Rs vo + of- then we have
1//
ven) S Po C min (v n) 1--10 n (1-
(24)
Deformation-liks stability. For inputs defined as signals E (22( over a continuous domain
Q S IR. == 2, the action of 'small' diffeomorphisms yp 12 -+ 52 as (p x)) = x (u)) is powerful diagnostic of performance of trainable CNNs [25], and key guiding principle for scattering representations 7]. these works, the basic deformation cost is measured as | ==
sup,, [[)) Il. We instantiate an equivalent of small deformations in our finiteddimensional
setting as follows.
- 4 fo Sa la(u) - o('') - (u-uu -o--w") u')l S clu-u'l3
(25)
where the differences are taken modulo d. For O, we recover the translation group described in Example 9 We can verify that & = 1 also corresponds to the translation group (due to the constraint that (u) (u') whenever f u'), thus the first non-trivial model corresponds to 2.
Proposition 14 (Upper bound on 7k(k) for deformations.). It holds 2 42 Moreover, | 2 nd for Rs 1.714, and
22n
d
Ta(k) SC
+ (k-nn)
(26)
(21) 20
for n < 1/4. In particular, 9-1 == (27))" 1-2 < 1 for 7j < 0.07, leading to an effective gain in sample complexity exponential in d, vo 1//0 ((7d/a); and B dn resulting in fast convergence in (24 even for large d.
We thus verify that small deformations, already with 2. provide a substantial gain relative to rigid translations, since 2 now grows exponentially with the dimension, rather than linearly. Let us remark that our small deformation model (25) acting on {1, differs important ways from diffeomorphisms acting on continuous domain. In our case they define unitary operators (since they are constructed as subsets of the permutation group), as opposed to diffeorphims, for which Ilyp ()))) * ||æ]]e=(0) generally. In other words, the 'deformations' in & are more akin to local shufflings the pixels rather than local distortions. That said, our model does roughly capture the size of small deformation classes. An interesting question for future work is to extend our framework to non-unitary transformations, which could accommodate appropriate discretisations of continuous diffeomorphisms.
6 Numerical Experiments
In this section, we provide simple numerical experiments on synthetic data which illustrate our theoretical results. In Figure [ we consider KRR on 000 training samples with inputs uniformly

---

KRR, perm ft, d m
block baoekkccccic__
KRR, block cyclic 6,
syelle
block 3
inv
block? ?
10-1
10
4
10 10' 10
107
102
107
107
131
Figure 1: Comparison of KRR with invariant and non non-invariant kernels. (left) permutation invarrian target with d = 6. comparison between various invariant kernels (cyclic, block-cyclic, and permutation groups). (center/right) invariant vs non non-invariant kernels invariant target functions with d 12, for block-cyclic groups G of two different sizes.
distributed on gd-1 and outputs generated according to a target non-smooth function f Sag" with 9" (z) 1 fw_ 2 0.73. where the averaging operator SG is over different groups each plot. The regularization parameter À is optimized on 5 000 test samples. We use the dot-product kernel function k<()) (u 1)k1 (u). where K1 the arc-cosine kernel of degree 1, which corresponds to an infinite-wiie width shallow ReLU network 9
When the target is permutation-invarian permutation invariance leads to the largest gain in sample complexity compared to those which use cyclic or block-cyclic groups. Since the permutation group has the largest cardinality, this is consistent with our finding that the gains may be of the order of the size of the group. Figures Saarrss[[eee [entter/rggh))) consider the example of cyclic translations on local blocks of size or 6 (Example I0 with or 6), and illustrate that the improvement in sample complexity happens later for s = 2 than = 6, which is consistent with the slower decays of ya obtained in (18) due to the larger number of cycles.
we can see in Figure Ileft) that the kernel based on
7 Discussion and Conclusion
We have studied how geometric invariance or stability assumptions on target functions enable more efficient learning, with improvements in sample complexity which may be large as the number of permutations considered in the group or set of elements to which the target is invariant or stable. In particular, this gain can be exponential in the dimension if we consider, e.g., all permutations, local translations on small blocks, or permutations that resemble small deformations. This last example provides a strong justification for seeking models and architectures that are stable deformations, a natural prior when learning functions on images [25]. In that respect, our results provide theoretical baseline to assess learning guarantees under geometric priors: by designing appropriate geometrically stable kernels, we simultaneously address approximation and generalisation errors within framework of convex optimization.
That said, while these gains may be large in practice, the obtained rates are still generically cursed by dimension if the target is non-smooth. In other words, invariance geoemtric stability allows us to express Lipschitz assumptions with respect to weaker metrics. While these stronger regularity assumptions result in important gains in sample complexity, they do not overcome the inherent difficulty of learning non-smooth structures in high tigh-diimnssoos. This suggests that further assump- tions may be needed to learn efficiently on high-dimensional geometric data, for instance with more structured forms of regularity beyond our invariant/stable setup, which may be exploited perhaps through architectures that involve local connectivity, hierarchy (which would explain the benefits of depth, as opposed to our current results), or feature learning [2] 4. [66] 21 27 A natural further question is to study stability to transformations that are not necessarily permutations, and which may then provide more realistic models of continuous deformations. Another interesting question is to study whether it is possible to adapt to general symmetries present the target, instead of encoding them in the model with appropriately designed kernel as done here.
10

---

Acknowledgments and Disclosure of Funding
LV and JB acknowledge partial support from the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF 1845360, NSF CHS- CHS-1901091, and Samsung Electronics.
References
[1] K. Atkinson and W. Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044. Springer Science Business Media, 2012.
[2] Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research (JMLR), (8(1):2296681 2017.
[3] F. Bach. Learning Theory from First Principles (draft). 2021.
[4] A. Bietti. Approximation and learning with deep convolutional models: kernel perspective. arXiv preprint arXiv:2102.1003: 2021.
[5] A. Bietti and F. Bach. Deep equals shallow for ReLU networks kernel regimes. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[6] A. Bietti and J. Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. Journal of Machine Learning Research (JMLR), 20(25)11499 2019.
[7] Bruna and S. Mallat. Invariant seattering convolution networks. IEEE Trunsactions on Puttern Analysis and Machine Intelligence (PAMI),
2013.
[8] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331 -368,,
13-66,,, 2007.
[9] Y. Cho and L. K. Saul. Kernel methods for deep learning. Advances in Neural Information Processing Systems (NIPS), 2009.
[10] C. Ciliberto, F. Bach, and A. Rudi. Localized structured prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[11] N. Cohen and A. Shashua. Inductive bias of deep convolutional networks through pooling geometry. arXiv preprint arXiv: 1605.0674, 2016.
[12] Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American mathematical sociery, 39(1):1-49) 2002.
[13] S. S. Du, Y. Wang, X. Zhai, S. Balakrishnan, R. Salakhutdinov, and A. Singh. How many samples are needed to estimate convolutional neural network? In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[14] C. Efthimiou and C. Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
[15] B. Elesedy and Zaidi. Provably striet generalisation benefit for equivariant models. arXiv preprint arXiv: 10333, 2021.
[16] A. Favero, F. Cagnetta, and M. Wyart. Locality defeats the curse of dimensionality in convolu- tional teacher-student scenarios. arXiv preprint arXiv:2106.08611 2021.
[17] S. Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research (JMLR), 21(205):1-38, 2020.
[18] Hastie, Tibshirani, and Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
[19] Z. Li, Y. Zhang, and S. Arora. Why are convolutional nets more sample-efficien than fully- connected nets? Proceedings of the International Conference on Learning Representations (ICLR), 2021.

---

[20] J. Maira.. P. Koniusz, Z. Harchaoui, and C. Schmid. Convolutional kerne networks. In Advances in Neural Information Processing Systems (NIPS), 2014.
[21] E. Malach and S. Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. In Proceedings of the International Conference Learning Repre- sentations (ICLR), 2021.
[22] S. Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-133 2012.
[23] Mei. T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021.
[24] H. N. Mhaskar and T. Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829 848, 2016.
[25] L. Petrini, A. Favero, M. Geiger, and M. Wyart. Relative stability toward diffeomorphisms in deep nets indicates performance. arXiv preprint wrxi:22105.02468. 2021.
[26] L. Pillaud-Vivien, A. Rudi, and F. Bach. Statistical optimality of stochastic gradient descent hard learning problems through multiple passes. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[27] T. Poggio. Mhaskar, Rosasco, B. Miranda, and Q. Liao. Why and when can deep-but not shallow-netword avoid the curse of dimensionality: a review. International Journal of Automation and Computing, 14(5):503-51) 519, 2017.
[28] N. C. Saldanha and C. Tomei. The accumulated distribution of quadratic forms on the sphere. Linear algebra and its applications, 245:335-351, 1996.
[29] A. J. Smola, Z. L. Ovari, and R. C. Williamson. Regularization with dot-product kernels. In Advances in Neural Information Processing Systems (NIPS), 2001.
[30] J. Sokolic, R. Giryes, G. Sapiro, and M. Rodrigues. Generalization error of invariant classi- fiers. In Proceedingy of the International Conference Artificial Intelligence and Statisties (AISTATS), 2017.
[31] M. J. Wainwright. High-dimensional statistics: A non-asympiotic viewpoint, volume 48. Cambridge University Press, 2019.
12


Reviews:
[{"review_id": "z_A-gfoim12", "reviewer": "Reviewer_qjVL", "summary": "This paper proposed a framework for analyzing the generalization behavior of kernel ridge regression under invariance and \"near-invariance\" assumptions with respect to group actions.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a highly inspirational and timely paper that shed new lights on learning under group actions.\n\nOriginality: The theoretical analysis under \"geometric stability\" in the context of kernel methods is unseen in previous literature, to the best of my knowledge. Technically, this work work is a novel combination of well-known techniques and new technical/combinatorial results. Related work are adequately cited.\n\nQuality: The submission is technically sound to the best of my knowledge.\n\nClarity: The submission is clearly written and well organized.\n\nSignificance: The results are established under specific assumptions and relied upon particular properties of e.g. spherical harmonics. This imposes limits on the generality of the results, but the qualitative nature of the results (e.g. dependence of generalization error on the \"effective dimension\") can be expected to hold in much wider contexts.  important? It is very likely that the results in this paper will open the door for deeper explorations in this direction for other researchers/practitioners.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The numerical experiments are more qualitative than quantitative; the tightness of the established theoretical results are not thoroughly addressed.\n\n- It's slightly confusing what the exponent $r$ means exactly in the notation $T^r_Kg$ in (A2). It can be guessed as a notation from functional calculus, but it would be good for the authors to confirm. It seems that (A2) is only used in the proof of Theorem 5 through reference [11].\n\n- I have some confusion regarding how specific the established results depend on the specific group (permutation group) and domain (sphere). Consider a case where a group acts on the sphere continuously and transitively (e.g. Hopf fibration), so the target invariant function is effectively defined on a lower-dimensional quotient domain. This would change the dimension factor $d$ and constant $\\nu_0$ simultaneously in e.g. (17). What do the theoretical results established in this paper look like on this \"quotient\" example (e.g. will they appear a bit conservative or pessimistic for this case)?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "QOAnek6JHy", "reviewer": "Reviewer_ey2p", "summary": "This paper considers the problem of learning a function $ f_\\ast \\colon \\mathbb{S}^{d-1} \\rightarrow R $ from i.i.d. data points $(x_1, y_1), \\dots (x_n, y_n)$ drawn from an unknown distribution $\\rho$ such that the marginal distribution of $x_i$ is over the sphere $S^{d-1}$ and $\\mathbb{E}(y \\mid x) = f_*(x)$. Further, they assume that $f_*$ is invariant under the action of a subgroup $G$ of $S_d$ (the group of permutations in $d$ elements), i.e.,\n$$ f(g \\cdot x) = f(x) \\qquad \\text{for all }g \\in G, x \\in \\mathbb{S}^{d-1}.$$\nThe main research question of the paper is whether one can derive better generalization error bound for methods that incorporate the invariance prior. They answer this question in the affirmative for Kernel ridge regression (KRR). For a given positive definite kernel $K$ and its associated Reproducing Kernel Hilbert Space (RKHS) $H_K,$ they study the standard KRR estimator\n$$\n\\widehat f_{\\lambda,K} = \\text{argmin} \\frac{1}{n}\\sum_{i=1}^n (f(x_i)-y_i)^2 + \\lambda \\|f\\|^2_{H_K}\n$$\nand consider two kernels:\n$$\nK(x, x') = \\kappa(\\langle x, x'\\rangle), \\quad K_G(x, x') = \\frac{1}{|G|} \\sum_{g \\in G} K(g \\cdot x, x') \\quad \\text{for }x, x' \\in \\mathbb{S}^{d-1}\n$$\nwith $\\kappa(u) \\leq 1$. For both of these kernels, the authors established sample complexity bounds for $\\mathbb{E} (\\widehat f_{\\lambda, K} - f_*)$ under reasonable assumptions. The bounds suggest that when $n \\rightarrow \\infty$, the risk given by $K_G$ is better by a factor of $\\frac{1}{|G|}$.\n\nThe authors extend the results to the case where $f^*$ is stable under small geometrical changes on the input, albeit with weaker statements.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies a relatively new and exciting question. It amasses theoretical evidence to support the use of learning methods that leverage invariance/symmetry. Unlike previous works, this paper studies a broader class of (nonsmooth) functions and assumes that the dimension is fixed and the number of samples grows.\n\nThe more substantial results derived in the paper suggest that incorporating invariance into the kernel gives gains of at most a constant factor (determined by the size of the group), and it is indicated in Section 3 that this is the best one can hope for. However, I believe the manuscript would benefit from a more in-depth explanation of optimality in this setting.\n\nAlthough the topic is highly technical, the paper is clear and reasonably easy to follow. The proofs seem to be mathematically rigorous. However, I did not check all the details. Overall the article is an interesting and well-written piece of work. Below I include a list of suggestions.\n\n- The theorem statements give upper bounds for both kernels. The results would be stronger if the statement for $\\widehat f_{\\lambda, K}$ included a lower bound.\n- The estimator is not guaranteed to be invariant under the action of the group. Do the authors think that this could bring additional gains? Elaborate on the main difficulties in developing theory where the invariance is enforced in the estimator f rather than the kernel.\n- L68 sudies -> studies.\n- L95 \",which\" -> \", which\"\n- L130 \". leading\" -> \". Leading\".\n- L141 rigression -> regression.\n- L233 traslations -> translations.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are stated in the last section. This paper studies a theoretical question with no explicit societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "ObVch5n21p8", "reviewer": "Reviewer_BHMR", "summary": "In this paper, the authors study the gain in sample complexity of using kernel ridge regression with invariant versus non-invariant kernels. The authors consider a target function that is invariant through the action of a subgroup $G$ of the symmetric group in $d$ dimensions, and compare learning it with (1) an inner-product kernel (non-invariant) and (2) an inner-product kernel made invariant by group averaging over $G$. They then assume some classical capacity (on kernel (1)) and source (on the invariant target) conditions, and apply a standard upper bound on the generalization error of KRR. The main technical contribution is to notice that using a representation of projection (already noticed in a previous work [1]),  one can bound the degrees of freedom of the invariant kernel to get a factor $\\nu_d (\\ell_n)$ improvement in sample complexity with invariant kernels in the upper bound. This factor depends on the size of the group and some spectral properties of the group, and the authors provide upper bounds for several examples. Two-insights: the improvement factor can be up to the size of the group, and this does not break the curse of dimensionality.\nThe authors finally considered approximate invariance (that also commute with the polynomials) and get a similar upper bound, with a slightly looser factor.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Exploiting invariance properties in the data is a central theme in machine learning, and is believed to play a major role in neural networks architecture for example. However, theoretical results are severely lacking and I find this work interesting and a great addition to the subject. The paper is well written and all the results are extensively discussed and interpreted. \n\nHowever, here is a few things that would need some clarifications for me to raise my rating: \n\n(1) Given the closeness to the paper [1], I would spend more time discussing and comparing the two works. Especially, the main insight of the proof (representation of projection) and the improvement factor were already claimed in [1], so I think the main contribution of this paper is to understand the dependency of this improvement factor on the structure of the group (in fixed $d$).\nI understand that $d$ fixed and large $d$ are two different regimes with very different techniques/assumptions (source and capacity conditions for example). However I don’t think the high dimensional regime is too naive (learn only low-degree polynomials) as it simply confirm a series of (non-rigorous) work that show that RF/KRR act as shrinkage operators with an inflated effective regularization (which seems to be a good approximation even for moderate/low  $d$). In the case of invariant kernel, this effective regularization is divided by $d^\\alpha$ and explain the improvement.\n\n(2) As far I understand, [1] considers not only invariance by translation (as written in your introduction), but more generally, subsets of the orthogonal group O(d). This includes group with infinite size. In [1], the \"degeneracy\" of the group instead of the cardinality of the group controls the sample size gain (for a group of degeneracy $\\alpha$, gain of factor $d^\\alpha$ in sample complexity). So even for some infinite group, there is only a finite sample size gain. In some cases (some subgroups of permutation of polynomial size, while you can consider exponentially sized groups in your paper), the degeneracy coincides with the size of the group. While [1] fully check the conditions only for invariance by translation, I expect their proof to extend to these cases (with the added requirement $n > O(d^\\alpha)$ if $\\alpha >1$). I think it will be useful to discuss how the improvement factor differ in the two settings: how does size, spectral properties and degeneracy of the group influence the improvement factor for $d$ fixed and $d$ large ? It would be great to clarify this in the introduction.\n\n(3) I would be more careful about claiming the factor improvement. A factor improvement in the generalization error upper bound does not necessarily imply a factor improvement in the actual generalization error. This would require to have a point wise lower bound with matching multiplicative constants (which is the case in the high-dimensional setting [1]). In particular, I am only aware of minimax lower bounds, but even in this case, the multiplicative constant can depend on the dimension. While I still believe these upper bounds are useful and match what happens in practice, I would add a paragraph discussing this point and different known lower bounds/or possible ways of obtaining them.\n\n\n[1] Learning with invariances in random features and kernel models, Mei, Misiakiewicz, Montanari (2021).\n\n\n---- Post-rebuttal ----\n\nThank you for the authors clarifications and for taking my suggestions. I am satisfied by the response and raised my rating to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "JTa4m9KV5GV", "reviewer": "Reviewer_MSM8", "summary": "In the context of kernel ridge regression, the authors study the improvements in generalization error for estimating target functions that are invariant or stable under a subset of symmetry transformations, when using kernels that have the same invariance or stability properties. Specifically, the authors study estimation of functions on the d-dimensional sphere, and consider symmetry transformations given by permutations of the d coordinates. The main results are generalization error upper bounds in two contexts: (1) When the subset of symmetry transformations form a subgroup of the symmetric group, the target function is exactly invariant under this subgroup, and the invariant kernel is given by a symmetrization of an inner-product kernel---Theorem 5. (2) When the subset of symmetry transformations can be arbitrary subset of permutations, and both the target function and kernel are given by an averaging operation applied to an initial function and inner-product kernel, with respect to some distribution over the transformations of this subset---Theorem 13.\n\nThe improvement in generalization error for the invariant kernel over the initial inner-product kernel comes from a reduction in the degrees of freedom associated to the ridge regressor, which may be upper-bounded by comparing the dimension of invariant spherical harmonics with that of all spherical harmonics at a given frequency k. In the analyzed setting where symmetry transformations are |G| permutations of d coordinates, the authors show that this ratio of dimensions converges to 1/|G| in the limit of large frequency k -> infty, which is the relevant limit for large sample sizes n -> infty. The authors quantify this rate of convergence in k for a number of different examples of symmetry subgroups.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper explores an interesting question, and provides a concrete set of results that demonstrate the possible improvements of exploiting invariance in the kernel design. The extension in section 5 to stability rather than exact invariance also feels important from a practical perspective. Technically, the generalization error bounds in terms of N_{K_G} are perhaps not too surprising, and the more significant technical contributions might be in how to control N_{K_G} and the dimension ratios gamma_d, as carried out in Section 4 and Appendix C.\n\nHowever, the insight provided by this paper also feels (to me) somewhat limited, for the following reasons:\n\n(1) It's not clear how sharp are the obtained generalization bounds---in particular how sharp is the method of bounding N_{K_G} in Lemma 4, and the further restriction of l_n in Theorem 5 such that the second term of this bound dominates the first. I would have appreciated one or two concrete examples where these analyses may be shown to correctly characterize the size of N_{K_G}(lambda) for the relevant choice of lambda.\n\n(2) As the authors recognize, since this dimension ratio nu_d in the risk bound (16) is lower-bounded by 1/|G|, the improvement in generalization error is not in the scaling dependence on n, but rather in how the \"constant\" depends on |G| and the dimension d. Thus the results are more significant for large subgroups or subsets |G|. I think this is fine, but then the analysis in Section 4 is a pointwise analysis over permutations in G, and thus doesn't really track well this dependence on d and |G|. For example, in the bound (17), nu_0 = 1/|G| can indeed be exponentially small in d, but can the leading constant C also be exponentially large in d? If n needs to be exponentially large in d for the statement \"nu_d(l_n) is approximately 1/|G|\" to hold, I think this detracts a bit from the relevance of the results.\n\n-----------------------------------------\n\nA couple other comments:\n\n(3) In the proof of Theorem 13, can the authors perhaps also provide a proof of the analogue of Lemma 3 (the approximation error) in this setting? The result of Lemma 3 feels more intuitive to me in the setting of exact invariance and where S is a projection onto a subspace, but is less clear to me in the \"geometric stability\" setting of Section 5.\n\n(4) Can the authors clarify what is the choice of h(sigma) in Proposition 14", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies kernel ridge regression in the case where the target function is invariant through the group action of $G$, a subgroup of the symmetric group. They explore how making the inner-product kernel invariant too can improve the sample complexity bounds. Furthermore they consider extensions to approximate invariance. One of the reviewers brought up the paper “Learning with invariances in random features and kernel models” by Mei et al. which has a number of overlapping messages. In their response, the authors clarified the technical relationship to this paper and the main differences are in the scaling regime and the types of permutation groups they can handle. Here they consider fixed $d$ and $n$ going to infinity, but can also work with large permutation groups whose size is exponential in $d$. This discussion should be incorporated into the next version of the paper. Overall the reviewers felt that this was a solid set of contributions on an important topic. 
Decision: Accept (Poster)