On the Sample Complexity of Learning under Invariance and Geometric Stability
Year: 2022

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.

heading: 1 Introduction
text: Learning from high-dimensional data is known to be statistically intractable without strong assumptions on the problem. A canonical example is learning Lipschitz functions, which generally requires a 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 as 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 X is the high-dimensional data domain, and G is a set of transformations σ : X → X , the learning task can be alleviated if one knows in advance that the target function f varies smoothly under transformations in G: |f(σ · x)− f(x)| is uniformly small over x ∈ X for σ ∈ G.
To further motivate this property, it is useful to view the data domain X as a space of signals X = L2(Ω;R) defined over a geometric domain Ω, such as a 2d grid. The set of transformations G can then be articulated in terms of Ω rather than X , a much simpler geometric object, and then lifted into X by composition: if σ : Ω → Ω, and x ∈ X then (σ · x)(u) := x(σ−1(u)) for every u ∈ Ω. The smoothness to transformations can thus be interpreted as a form of geometric stability.
In this paper, we quantify the sample complexity gains brought by geometric stability. Concretely, we consider target functions f defined on the sphere X = Sd−1 in d dimensions with finite L2(Sd−1) norm. In this case, we view the geometric domain as the discrete 1d grid Ω = [1, . . . , d], and consider geometric transformations G as subsets of the symmetric group of permutations of d
∗Center for Data Science, New York University. †Courant Institute for Mathematical Sciences, New York University. ‡Center for Data Science and Courant Institute for Mathematical Sciences, New York University.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
elements. Given a set G (not necessarily a group), we consider the smoothing operator given by SGf(x) = 1 |G| ∑ σ∈G f(σ · x) for f ∈ L 2(Sd−1), and assume that our target function f is geometrically stable, in the sense that f = SGg for some g ∈ L 2(Sd−1). In words, the smoothing operator SG replaces the prediction f(x) by the average over transformations of x. In particular, functions which are invariant under the action of σ ∈ G, namely
f(σ · x) = f(x), σ ∈ G, x ∈ Sd−1, (1)
are also stable, with f = SGf .
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 a factor of the order of the size of the group when the sample size is large enough (Section 3).
• We study how this improvement factor varies with sample size, in terms of the structure of the group and on 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. In contrast to [23], we consider the dimension to be fixed and study 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 as the scattering transform [22, 7], or convolutional kernels [6, 20]. While these works characterise the stability in terms of the dyadic structure of convolutional filters (such as wavelets), they do not cover a statistical analysis of sample complexity. Similarly, models of compositional functions such as those in [11, 24, 27] study the benefit of hierarchical representations with local connectivity for approximation, while [19, 21] study benefits of local connectivity with optimization-based 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. [15] also sudies benefits of group invariance, but focuses on linear models, and only considers interpolating estimators. [30] 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.

heading: 2 Preliminaries
text: 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 a supervised learning problem where the data distribution ρ on input-label pairs (x, y) is such that x ∈ Sd−1 and E[y|x] = f∗(x) for some target function f∗in L2(Sd−1). For simplicity, we will assume that x is uniformly distributed on the sphere, and denote the uniform measure on Sd−1 by dτ . We consider a regression setup with L2 risk given by
R(f) = E(x,y)∼ρ [ (f(x)− y)2 ] .
For a given estimator f̂n based on n samples from ρ, the goal is then to obtain generalization bounds as a function of n on the excess risk
E[R(f̂n)]−R(f ∗) = E[‖f̂n − f ∗‖2L2(dτ)], (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 f∗ and of a kernel function in appropriate L2 bases, which then relate function regularity and decays of Fourier coefficients.
Harmonic analysis on the sphere. When considering functions in L2(dτ), an appropriate choice of orthonormal basis is that of spherical harmonic polynomials [1, 14]. More precisely, denote {Yk,j} N(d,k) j=1 denote an orthonormal basis of the space Vd,k of spherical harmonics of degree k, i.e., homogeneous harmonic polynomials of degree k, where N(d, k) = 2k+d−2k ( k+d−3 d−2 ) . Then, the collection {Yk,j : k ≥ 0, j = 1, . . . , N(d, k)} forms an orthonormal basis of L 2(dτ), so that any function f ∈ L2(dτ) may be written
f(x) = ∑
k≥0
N(d,k) ∑
j=1
ak,jYk,j(x), (3)
with ∑
k ∑N(d,k) j=1 a 2 k,j < ∞. Similarly, any dot-product kernel K(x, x ′) = κ(〈x, x′〉) on the sphere may be written
κ(〈x, x′〉) = ∑
k≥0
µk
N(d,k) ∑
j=1
Yk,j(x)Yk,j(x ′), (4)
where µk is given by µk = ωd−2 ωd−1 ∫ 1 −1 κ(t)Pd,k(t)(1−t 2)(d−3)/2dt. Here, ωp−1 is the surface measure of the sphere in p dimensions, and Pd,k are Legendre or Gegenbauer polynomials of degree k in d dimensions (normalized with Pd,k(1) = 1),which form an orthogonal basis of L
2([−1, 1], dw), with dw(t) = (1− t2)(d−3)/2dt. When the kernel K is positive definite and is used in the context of kernel ridge regression with data uniformly distributed on the sphere, then the µk also correspond to the eigenvalues of the covariance operator. These eigenvalues and their decay then control the statistical properties of the kernel ridge regression estimator [8].
Spherical harmonics and group-invariant functions. In order to describe harmonic decompositions of functions satisfying the group invariance property (1) for a discrete group G, we follow [23] and define the symmetrization operator
SGf(x) = 1
|G|
∑
σ∈G
f(σ · x). (5)
This operator acts as a projection from L2(dτ) to a subset thereof which contains invariant functions. It can be shown that the spaces Vd,k of spherical harmonics of degree k are stable by SG [23], and we may then define an orthonormal basis of V d,k := SGVd,k consisting of invariant spherical harmonics {Y k,j} N(d,k) j=1 . We then have the following lemma.
Lemma 1 (Representation of projection [23]). For any k ≥ 0, we have
γd(k) := N(d, k)
N(d, k) =
1
|G|
∑
σ∈G
Ex [Pd,k(〈σ · x, x〉)] . (6)
The quantity γd(k) will play an important role in determining the gains in sample complexity brought by invariance. We will show in Section 4 that γd(k) converges to 1/|G| for large k, with an asymptotic behavior that is governed by spectral properties of the elements of the group.

heading: 3 Sample Complexity of Invariant Kernels
text: 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 nonparametric rates of convergence that illustrate the gains achievable with invariant kernels compared to non-invariant ones.
Kernel ridge regression (KRR) and invariant kernels. For a positive definite kernel K with
RKHS HK , we consider the KRR estimator f̂λ given by
f̂λ := arg min f∈HK
1
n
n ∑
i=1
(f(xi)− yi) 2 + λ‖f‖2HK . (7)
We consider the following kernels, which we assume positive definite, given for x, x′ ∈ Sd−1 by
K(x, x′) = κ(〈x, x′〉), KG(x, x ′) =
1
|G|
∑
σ∈G
κ(〈σ · x, x′〉), (8)
with κ(u) ≤ 1. A common example for κ is the arc-cosine kernel [9], which arises from infinite-width shallow neural networks with ReLU activations. The following integral operator defined on L2(dτ) and its eigen decomposition play an important role for the statistical and approximation properties of kernel methods:
TKf(x) =
∫
K(x, x′)f(x′)dτ(x′). (9)
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 TKG are jointly diagonalized. They admit the same eigenvalues µk as in (4), with multiplicity N(d, k) for TK and N(d, k) for TKG .
The decay of the eigenvalues µk controls the smoothness of functions in the RKHS, for instance when µk decays polynomially, TK behaves similarly to powers of the Laplacian on the sphere, leading to functional spaces similar to Sobolev spaces. For the example of the arc-cosine kernel, µk decays as k−d−2. leading to an RKHS containing functions with d/2 + 1 bounded derivatives [2].
Approximation error. The approximation error of kernel methods is often controlled by the following quantity (e.g., [3, 12]):
AH(λ, f ∗) = inf f∈H ‖f − f∗‖2L2(dτ) + λ‖f‖ 2 H, (10)
where f∗ is a target function in L2(dτ), and H is a given RKHS. In particular, if f∗ is smooth enough so that f∗ ∈ H, then we have AH(λ, f ∗) ≤ λ‖f∗‖2H, while if f ∗ /∈ H, e.g., if f∗ is only Lipschitz, then AH(λ, f ∗) typically grows much faster with λ. We now show a useful result for invariant targets, 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∗ = SGf ∗, then we have
AHK (λ, f ∗) = AHKG (λ, f ∗). (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., [3, 18]):
NK(λ) = Tr(ΣK(ΣK + λI) −1) =
∑
m≥0
λm λm + λ , (12)
where ΣK = Ex [K(x, ·)⊗HK K(x, ·)] is the covariance operator and (λm)m≥0 its eigenvalues, taking multiplicity into account, which are the same as those of TK when data is distributed according to dτ [8]. We then obtain the following simple result relating NKG to NK . Lemma 4 (Degrees of freedom for K and KG.). For any ℓ ≥ 0, we have
NKG(λ) ≤ D(ℓ) + νd(ℓ)NK(λ),
where D(ℓ) := ∑
k<ℓ N(d, k) and νd(ℓ) := supk≥ℓ γd(k), with γd given in (6).
This suggests that for a fixed ℓ, the effective dimension of KG is controlled by a factor νd(ℓ) times that of K, up to a finite fixed dimension D(ℓ). For difficult non-parametric problems which require small λ at large sample sizes, the second term will tend to dominate, so that having a small νd(ℓ) 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: NK(λ) ≤ CKλ −1/α with α > 1. (A2) source condition: there exists r > α−12α and g ∈ L 2(dτ) with ‖g‖L2(dτ) ≤ Cf∗ such
that f∗ = T rKg.
(A3) invariance: f∗ is G-invariant.
(A4) problem noise: ρ is such that Eρ[(y − f ∗(x))2|x] ≤ σ2ρ.
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 λm of TK decay as k
−α. On the sphere, α = 2sd−1 corresponds to having s bounded derivatives, e.g., we have s = d/2 + 1 for the arc-cosine kernel. The parameter r in (A2) defines the regularity of f∗ relative to that of the kernel: r = 1/2 corresponds to f∗ ∈ HK , while larger (resp. smaller) r implies f
∗ is more (resp. less) smooth. The condition on r is needed for our specific bound, which is based on [3, Proposition 7.2], but may be bypassed using different algorithms or analyses [17, 26]. We now present our bound on the excess risk.
Theorem 5 (Generalization of invariant kernel.). Assume (A1-4). Let νd(ℓ) be as in Lemma 4, or an upper bound thereof, and assume ν0 := infℓ≥0 νd(ℓ) > 0. Let n ≥ max {
‖f∗‖2∞/σ 2 ρ, (C1/ν0)
α 2αr+1−α
}
, and define
ℓn := sup{ℓ : D(ℓ) ≤ C2νd(ℓ) 2αr 2αr+1n 1 2αr+1 }. (13)
We then have, for λ = C3(νd(ℓn)/n) α/(2αr+1),
E[R(f̂λ)−R(f ∗)] ≤ C4
(
νd(ℓn)
n
) 2αr
2αr+1
. (14)
In the same setting, KRR with kernel K and λ = C3n −α 2αr+1 achieves E[R(f̂λ)−R(f ∗)] ≤ C4n −2αr 2αr+1 , where C3, C4 are the same constants as for the invariant kernel. Here, the constants C1:4 only depend on the parameters of assumptions (A1-4).
The theorem shows that the generalization error for the invariant kernel behaves as if it effectively had access to n/νd(ℓn) samples, so that νd(ℓn) plays the role of an effective inverse sample complexity gain at sample size n. Note that νd(ℓn) ≤ 1 and νd is decreasing, so that we always have some improvement in sample complexity, and this gets better when ℓn is large. In particular, we show in Section 4 that γd(k), and hence νd(ℓ) converge to 1/|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 in d.
Asymptotic estimates of the effective gain νd(ℓn). We now study the asymptotic behavior of the effective gain factor νd(ℓn) when n → ∞, by considering a case where an asymptotic equivalent of νd(ℓ) in ℓ is known:
νd(ℓ) ≈ ν0 + cℓ −β .
In Section 4, we obtain such asymptotics with ν0 = 1/|G|, and a rate β that depends on spectral properties of the elements of G, as well as upper bounds with possibly faster rates β at the cost of larger ν0. In Appendix B.5, we show that we may leverage this to obtain the following asymptotic estimate of the effective gain νd(ℓn):
νd(ℓn) ≤ ν0 + Cmin { (ν2αr0 n) −β (d−1)(2αr+1) , n −β (d−1)(2αr+1)+2βαr } . (15)
Notice that when β ≪ d, both exponents of n display a curse of dimensionality, but this curse goes away as β grows. Note also that the first exponent yields a faster rate, but one that is only achieved for large n due to the factor ν2αr0 , which may be small for large groups.
Curse of dimensionality and optimality. Note that the bound obtained in Theorem 5 is still cursed for an invariant target f∗, in the sense that the exponent in the rate is of order 1/d when f∗ is only assumed to be Lipschitz. Indeed, a Lipschitz assumption on f∗ corresponds to taking r and α such that 2αr ≈ 2/(d− 1), which makes the source condition (A2) similar to a bound on ‖∇f∗‖L2(dτ).
This then leads to a cursed rate n−2/(2+d−1), raising the question of whether this can be improved. We note that since γd(k) = Ω(1/|G|) (as we show in Section 4), the asymptotic decays (as a function of k) of the coefficients of f∗ and of the eigenvalues of TKG are similar to those for the non-invariant case, which implies that these rates cannot be improved (see, e.g., [8]). In Appendix B.6, we show that our bounds with an improvement in sample complexity by a 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-parametric learning of invariant functions with similar kernels. They consider a high-dimensional regime where d → ∞ with sample sizes in polynomial scalings n ≈ ds for some s. They then show that if γd(k) = Θd(d
−α) as d → ∞, for some α > 0 (which they call degeneracy), then the invariant kernel can learn polynomials of degree ℓ with n ≈ dℓ−α while the non-invariant kernel needs n ≈ dℓ samples. In some cases, such as the cyclic group, [23] show α = 1 and hence the gain of a factor dα = d is 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 → ∞, and may lead to gains by exponential factors if |G| is large, at least asymptotically.

heading: 4 Counting Invariant Polynomials
text: In this section, we study the asymptotic behavior of γd(k), given in (6), when k → ∞ 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, as described in Section 3. Denoting γd,σ(k) := Ex [Pd,k(〈σ · x, x〉)], we will show that γd,σ(k) vanishes for large k for any σ that is not the identity. This implies that γd(k) converges to 1/|G|, since we trivially have γd,Id(k) = Pd,k(1) = 1. We further characterize the asymptotic behavior of γd(k) in terms of properties of the group elements. In the following we consider the case of G being a subgroup of Sd, the groups of permutations on d elements.
Decay of γd,σ(k). Our main insight is to leverage the fact that when σ is not the identity, then the random variable zσ = 〈σ ·x, x〉 when x ∼ τ admits a density on [−1, 1], which we denote qσ . This by itself will prove sufficient to show that γd,σ(k) decays for large k, thanks to the oscillatory behavior of Pd,k. We can then further characterize its asymptotic behavior by studying the singularities of qσ , leveraging the seminal work of Saldanha and Tomei [28]. In particular, these depend on spectral properties of the matrix associated to σ. We summarize this in the next proposition.
Proposition 6 (Asymptotic behavior of γd,σ(k).). Let Aσ be the matrix associated to σ 6= Id, that is such that σ · x = Aσx. Denote by Λσ the set of (complex) eigenvalues of Aσ, and by mλ the multiplicity of λ ∈ Λσ. When k → ∞, we have the asymptotic equivalent γd,σ(k) = ∑
λ∈Λσ γd,σ,λ(k),
where
γd,σ,λ(k) .
{
k−d+mλ + o(k−d+mλ) , if λ ∈ {±1} , k−d+mλ+4 + o(k−d+mλ+4) , otherwise, (16)
where . hides constants that may depend on d, σ and λ.
Every permutation σ ∈ Sd (where Sd 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 λ = e2πiθ, and one can verify that necessarily θ = pq ∈ Q. Furthermore, assuming w.l.o.g. that q is prime, such eigenvalue appears whenever σ contains a cycle of length a multiple of q. In particular, the multiplicity of the eigenvalue 1, m1, corresponds to the total number of cycles in such a decomposition, which we will denote by c(σ). Then γd,σ(k) can be controlled as follows.
Corollary 7 (Decay of γd,σ(k)). Let σ 6= Id, and let c(σ) denote the number of cycles in σ. Then,
γd,σ(k) .
{
k−d+c(σ) , if c(σ) > d+32 , k−d/2+6 , otherwise .
Decay on specific subgroups. We may now use Corollary 7 to study the asymptotic behaviour of γd(k) as k → ∞ for various choices of subgroups of Sd, using the following result. Corollary 8 (Upper bounds with permutation statistics). Let G be a subset of Sd and define ζ(G, s) := |{σ ∈ G : c(σ) > s}| for s ∈ [d− 1]. Then, for any s, we have
γd(k) ≤ ζ(G, s)
|G| +O
( k−d+max{s, d/2+6} ) , (17)
with equality if s is such that ζ(G, s) = 1.
Note that such an upper bound immediately yields a similar upper bound for νd(ℓ) as defined in Section 3, which then controls the effective gain in sample complexity in Theorem 5. Indeed, (17) implies that there is a constant C such that for all k > 0, γd(k) ≤ ζ(G, s)/|G|+Ck −d+max{s,d/2+6}. Since this upper bound decreases with k, we obtain
νd(ℓ) ≤ ζ(G, s)
|G| + Cℓ−d+max{s,d/2+6}.
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 νd(ℓn) as in (15), with asymptotic gain ν0 = ζ(G,s) |G| and rate β = d−max{s, d/2 + 6}. Example 9 (Translations). Let G = Cd be the cyclic group on d elements. Then it holds
γd(k) = 1
d +O
( k−d/2+6 ) .
This follows by noticing that every translation σ (but the identity) satisfies c(σ) ≤ d/2. This leads to an asymptotic gain ν−10 = d and β = d/2− 6 leads to fast convergence in (15) even when d is large. Example 10 (Local translations). Let d = s · r (with r, s ≥ 5 for simplicity), and consider the group composed of traslations over r blocks of coordinates of size s; i.e., the block-cyclic group
G = {σ : σ = σ(1) ◦ · · · ◦ σ(r)}
where each σ(i) is a translation over the set {(i− 1)s+ 1, . . . , is}, for i ∈ [r]. Then it holds
γd(k) = 1
sr +O
( k−s/2+1 ) . (18)
This follows by noticing that every local translation σ (but the identity) satisfies c(σ) ≤ (d− s)+ s/2. Here the asymptotic gain is ν−10 = s
r = sd/s, which can be exponential in d when s is small. We have β = s/2 − 1, which leads to much slower convergence than the translation case, unless s is large and of order d.
Example 11 (Full permutation group). For the case of G = Sd, we can split the group based on the value of Fix(σ), the number of elements fixed by a permutation σ. Denote
ξ(G, s) := |σ ∈ G : Fix(σ) > s| = d ∑
j=s+1
(
d
j
)
!(d− j) .
for s ∈ [d− 1], where !k denotes the k-th subfactorial. Then we have
γd(k) ≤ ξ(G, s)
d! +O
( k−d/2+max{s/2, 6} ) ,
with equality for s = d − 1. This follows from the fact that c(σ) ≤ Fix(σ) + (d − Fix(σ))/2. In particular, it follows
γd(k) ≤ 2
(s+ 1)! +O
( k−d/2+max{s/2, 6} ) .
When considering the full group, we may get a large asymptotic improvement of order ν−10 = |G| = d! in sample complexity, but a slow convergence with β = −1 as per Corollary 8 (assuming d large enough). Using different values of s may yield different upper bounds with faster convergence rates β = d/2−max{s/2, 6}, but smaller asymptotic gains in sample complexity, given by ν−10 = (s+1)!/2. For instance, with s = d/2 and d large enough, we have β = d/4, leading to a potentially fast convergence rate in 15 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.

heading: 5 Beyond Group Invariance: Geometric Stability
text: In this section, we study gains in sample complexity when the target function f∗ is not fully invariant to a group, but may be stable under small geometric changes on the input. We formalize this by considering a similar averaging operator SG, but we allow G to be a generic set of permutations instead of a group, and allow for a weighted average:
SGf(x) := ∑
σ∈G
h(σ)f(σ · x), (19)
where h(σ) ≥ 0 for all σ ∈ G and ∑ σ∈G h(σ) = 1. We assume that G is “symmetric”, i.e., σ −1 ∈ G when σ ∈ G and h(σ−1) = h(σ), so that SG is self-adjoint. In this case, images of SG 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 a 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 a more structured set G of permutations that resemble local deformations, consisting of both a global translation as well as different local translations at different scales, as we describe below.
Spectral properties of SG. Note that in this setup, we no 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 SG). There exists a basis of spherical harmonics Y k,j , for k ≥ 0, and j = 1, . . . , N(d, k), in which the operator SG is diagonal, with eigenvalues λk,j ≥ 0. In analogy to Lemma 1, we have
γd(k) := N(d, k) −1
N(d,k) ∑
j=1
λk,j = ∑
σ∈G
h(σ)Ex [Pd,k(〈σ · x, x〉)] . (20)
We also define νd(ℓ) := supk≥ℓ γd(k).
Sample complexity of stable kernel. In analogy to Section 3, we may consider a stable kernel
KG(x, x ′) =
∑
σ∈G
h(σ)κ(〈σ · x, x′〉). (21)
Then, it is easy to check that the integral operator of KG is given by TKG = SGTK . 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, we may represent favorable targets f∗ as those whose coefficients decay similarly at each frequency k to those of SG, by viewing it as a smoothing of some L 2 function g∗, i.e., f∗ = SrGg ∗ for some exponent r. With this in mind, we make the following assumptions, replacing assumptions (A1-3) of Section 3.
(A5) capacity: the eigenvalues (ξm)m≥0 of TK satisfy ξm ≤ C(m+ 1) −α.
(A6) source condition: there exists r > α−12α and g ∈ L 2(dτ) with ‖g‖L2(dτ) ≤ Cf∗ such
that f∗ = SrGT r Kg.
Note that (A6) corresponds to a standard source condition with the kernel KG (since T r KG = SrGT r K ), yet it reveals how KG jointly performs smoothing on the sphere, through TK , as well as on permutations through SG. While these two forms of smoothing appear “entangled” in this assumption, one may balance them by choosing different levels of smoothing in the kernel function κ, or by averaging multiple times in (21). Assumption (A5) is needed for obtaining a variant of Lemma 4, and implies (A1) with CK ∝ C 1/α. We then obtain the following generalization bound.
Theorem 13 (Generalization with geometric stability.). Assume (A4-6), and assume ν0 := infℓ≥0 νd(ℓ) > 0. Let n ≥ max(‖f ∗‖2∞/σ 2 ρ, (C1/ν0) 1/(2αr+1−α) ), and define
ℓn := sup{ℓ : D(ℓ) ≤ C2νd(ℓ) 2r 2αr+1n 1 2αr+1 }. (22)
We then have, for λ = C3(νd(ℓn) 1/α/n)α/(2αr+1),
E[R(f̂λ)−R(f ∗)] ≤ C4
(
νd(ℓn) 1/α
n
) 2αr 2αr+1
. (23)
In the same setting, KRR with kernel K achieves a similar bound with νd(ℓn) 1/α replaced by 1, but with a possibly smaller constant C4. Here, the constants C1:4 only depend on the parameters of assumptions (A4-6).
Note that the obtained generalization bound is very similar to Theorem 5, but with a factor νd(ℓn) 1/α instead of νd(ℓn). This is due to the fact that in contrast to the invariant case, where γd(k) in (6) can help precisely control the number of invariant spherical harmonics, in this case γd(k) as computed in (20) can only give information about the sum of the eigenvalues λk,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 (α ≈ 1) but can be more pronounced for smooth kernels with fast decays (large α). Note also that the different source condition (A6) leads to a different approximation error, and thus to an approximation-estimation trade-off related to stability, which does not appear in the group-invariant case. More precise estimates of the decays of λk,j may help characterize this tradeoff more formally, and we leave this question to future work. As in (15), we may derive an estimate of νd(ℓn), namely if νd(ℓ) ≈ ν0 + cℓ −β , then we have
νd(ℓn) ≤ ν0 + Cmin { (ν2r0 n) −β (d−1)(2αr+1) , n −β (d−1)(2αr+1)+2βr } . (24)
Deformation-like stability. For inputs x defined as signals x ∈ L2(Ω) over a continuous domain Ω ⊆ Rs, s = 1, 2, the action of ‘small’ diffeomorphisms ϕ : Ω → Ω as (ϕ · x)(u) = x(ϕ−1(u)) is a powerful diagnostic of performance of trainable CNNs [25], and a key guiding principle for scattering representations [22, 7]. In these works, the basic deformation cost is measured as ‖ϕ‖ := supu ‖∇ϕ(u) − I‖. We instantiate an equivalent of small deformations in our finite-dimensional setting as follows.
Φε := {σ ∈ Sd : |σ(u)− σ(u ′)− (u− u′)| ≤ ε|u− u′|} , (25)
where the differences are taken modulo d. For ε = 0, 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) 6= σ(u′) whenever u 6= u′), thus the first non-trivial model corresponds to ε = 2.
Proposition 14 (Upper bound on γd(k) for deformations.). It holds Φ −1 2 = Φ2. Moreover, |Φ2| ≥ τ d for τ ≈ 1.714, and
γd(k) ≤ C
(
e2η
(2η)2ητ1−2η
)d
+O ( k−ηd )
(26)
for η < 1/4. In particular, τ̃−1 := e 2η
(2η)2ητ1−2η < 1 for η < 0.07, leading to an effective gain in
sample complexity exponential in d, ν −1/α 0 = Θ(τ̃ d/α); and β = ηd 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, d} differs in important ways from diffeomorphisms acting on a 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 ‖ϕ · x‖L2(Ω) 6= ‖x‖L2(Ω) generally. In other words, the ‘deformations’ in Φε are more akin to local shufflings of 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.

heading: 6 Numerical Experiments
text: In this section, we provide simple numerical experiments on synthetic data which illustrate our theoretical results. In Figure 1, we consider KRR on 5 000 training samples with inputs uniformly
distributed on Sd−1, and outputs generated according to a target non-smooth function f∗ = SGg ∗, with g∗(x) = ✶{w⊤∗ x ≥ 0.7}, where the averaging operator SG is over different groups in each plot. The regularization parameter λ is optimized on 5 000 test samples. We use the dot-product kernel function κ(u) = (u+ 1)κ1(u), where κ1 is the arc-cosine kernel of degree 1, which corresponds to an infinite-width shallow ReLU network [9].
When the target is permutation-invariant, we can see in Figure 1(left) that the kernel based on 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 1(center/right) consider the example of cyclic translations on local blocks of size 2 or 6 (Example 10 with s = 2 or 6), and illustrate that the improvement in sample complexity happens later for s = 2 than s = 6, which is consistent with the slower decays of γd obtained in (18) due to the larger number of cycles.

heading: 7 Discussion and Conclusion
text: We have studied how geometric invariance or stability assumptions on target functions enable more efficient learning, with improvements in sample complexity which may be as 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 to deformations, a natural prior when learning functions on images [25]. In that respect, our results provide a theoretical baseline to assess learning guarantees under geometric priors: by designing appropriate geometrically stable kernels, we simultaneously address approximation and generalisation errors within a 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 or 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-dimensions. This suggests that further assumptions 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, 16, 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 in the target, instead of encoding them in the model with an appropriately designed kernel as done here.
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-1901091, and Samsung Electronics.

Review summaries:
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. The authors finally considered approximate invariance (that also commute with the polynomials) and get a similar upper bound, with a slightly looser factor.

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.  The 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.

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., $$ f(g \cdot x) = f(x) \qquad \text{for all }g \in G, x \in \mathbb{S}^{d-1}.$$ The 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 $$ \widehat f_{\lambda,K} = \text{argmin} \frac{1}{n}\sum_{i=1}^n (f(x_i)-y_i)^2 + \lambda \|f\|^2_{H_K} $$ and consider two kernels: $$ K(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} $$ with $\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|}$.  The authors extend the results to the case where $f^*$ is stable under small geometrical changes on the input, albeit with weaker statements.