Learning with invariances in random features and kernel models

Introduction

Convolutional neural networks are the state-of-the-art architecture for image classification and related computer vision tasks, and they are believed to exploit the translation invariance in a crucial way [KSH12]. Consider the simple example of two-layer convolutional networks with global average pooling. The network computes a nonlinear convolution of $N$ filters ${\bm{w}}_{1},\dots,{\bm{w}}_{N}$ with the image ${\bm{x}}$. The results are then combined linearly with coefficients $a_{1},\dots,a_{N}$:

This simple convolutional network can be compared with a standard fully-connected two-layer network with the same number of parameters: $f_{{\sf NN}}({\bm{x}})=\sum_{i=1}^{N}a_{i}\sigma(\langle{\bm{w}}_{i},{\bm{x}}\rangle)$. It is clear that —when the target function $f_{*}$ is translation invariant— the convolutional model $f_{{\sf CNN}}({\bm{x}})$ is at least as powerful as $f_{{\sf NN}}({\bm{x}})$ in terms of approximation, since it is invariant by construction (see Appendix A.1 for a simple formal argument).

In order to gain some insights on the behavior of actual neural networks, we consider two classes of linear ‘overparametrized’ models: invariant random features models and invariant kernel machines. We next describe these two approaches.

Invariant kernel machines. We then consider kernel ridge regression (KRR) in the reproducing kernel Hilbert space (RKHS) defined by a ${\mathcal{G}}_{d}$-invariant kernel. By this we mean a kernel $H\in L^{2}(\mathcal{A}_{d}\times\mathcal{A}_{d})$ such that, for all $g,g^{\prime}\in{\mathcal{G}}_{d}$, the following folds for every ${\bm{x}}_{1},{\bm{x}}_{2}$:

Note that, as a consequence of this property, any function that is not in $L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})$ (i.e. any function that is not invariant) has infinite RKHS norm: indeed this provides an alternate characterization of invariant kernel methods. Among ${\mathcal{G}}_{d}$-invariant kernels, we focus on the subclass that is obtained by averaging an inner product kernel over the group ${\mathcal{G}}_{d}$

Invariant kernel machines can be regarded as large-width ($N\to\infty$) limits of invariant random features methods. Vice versa, the latter can be regarded as randomized approximations of invariant kernel methods. Moreover, invariant kernel methods also capture the large-width limits of other models, for instance, neural tangent models associated to convolutional networks (c.f. Section A.3).

We focus on a type of groups ${\mathcal{G}}_{d}$ that we call groups of degeneracy $\alpha$.

Let $V_{d,k}$ be the subspace of degree-$k$ polynomials that are orthogonal to polynomials of degree at most $(k-1)$ in $L^{2}(\mathcal{A}_{d})$, and denote by $V_{d,k}({\mathcal{G}}_{d})$ the subspace of $V_{d,k}$ formed by polynomials that are ${\mathcal{G}}_{d}$-invariant. We say that ${\mathcal{G}}_{d}$ has degeneracy $\alpha$ if for any integer $k\geq\alpha$ we have $\dim(V_{d,k}/V_{d,k}({\mathcal{G}}_{d}))\asymp d^{\alpha}$ (i.e., there exists $0<c_{k}\leq C_{k}<\infty$ such that $c_{k}\leq\dim(V_{d,k}/V_{d,k}({\mathcal{G}}_{d}))/d^{\alpha}\leq C_{k}$ for any $d\geq 2$).

This definition includes as special cases the cyclic group for one and two-dimensional signals (see Section 2), which have both degeneracy $1$.

We compare invariant methods to standard (non-invariant) random features models with inner product activation, defined as

and standard inner product kernels $H({\bm{x}}_{1},{\bm{x}}_{2})=h_{d}(\langle{\bm{x}}_{1},{\bm{x}}_{2}\rangle/d)$. For groups with degeneracy $\alpha\leq 1$, we obtain a fairly complete characterization of the gain achieved by using invariant models, when the target function is an arbitrary invariant function $f_{*}\in L^{2}(\mathcal{A}_{d};{\mathcal{G}}_{d})$.

These results are precisely presented in Theorem 1 and summarized in Table 1. We establish the same gain for invariant kernel methods in Theorem 2. While we focused in this paper on groups with degeneracy $\alpha\leq 1$ (which include our primary motivating examples, cyclic group in one or two dimensions), we expect similar results to hold for groups with $\alpha>1$. We defer this to future work.

Output symmetrization and data augmentation are two alternative approaches to incorporate invariances in machine learning models. We show that the performance of output symmetrization of standard KRR does not improve over standard KRR, and hence is sub-optimal compared to invariant KRR. On the other hand, it was shown that (c.f. [LWY+19]) data augmentation is mathematically equivalent to invariant KRR for discrete groups. As a consequence, our theoretical results characterize the statistical gain by performing data augmentation.

It is important to mention that our treatment omits an important characteristic of convolutional architectures: the fact that the filters ${\bm{w}}_{i}$ of Eq. (1) have a short window size $q\ll d$. Namely, they have only $q$ non-zero entries, for instance the first $q$ entries. Using short-window filters has some interesting consequences, which can be investigated using the same approach developed here. We will report on these in a forthcoming article, and instead focus here on the impact of invariance.

Our analysis is enabled by a simple yet important observation, which might generalize to other settings. The subspaces $V_{d,k}$ of degree-$k$ polynomials (see Definition 1) are eigenspaces for inner product kernels. At the same time, they are preserved under the symmetry group ${\mathcal{G}}_{d}$. Namely, define $f^{(g)}({\bm{x}})=f(g\cdot{\bm{x}})$, we have $f^{(g)}\in V_{d,k}$ for any $f\in V_{d,k}$, $g\in{\mathcal{G}}_{d}$. This observation is crucial in determining the eigendecomposition of the relevant kernels.

Let us finally emphasize, that the factor-$d$ gain in sample size for degeneracy-one groups is not correctly predicted by a naive ‘data augmentation heuristics’. The latter would suggest a gain of the order of $|{\mathcal{G}}_{d}|$ or of the size of orbits of ${\mathcal{G}}_{d}$. As shown by the example of band limited functions (see below) $|{\mathcal{G}}_{d}|$ can be $\infty$ but the degeneracy can still be one (and hence the gain is $d$).

A number of mathematical works emphasized the role of invariance in neural network architectures. Among others, [Mal12, BM13, Mal16] propose architectures (‘deep scattering networks’) that explicitly achieve invariance to a rich group of transformations. However, these papers do not characterize the statistical error of these approaches.

The recent paper [LZA20] constructs a simple data distribution on which a gap is proven between the sample complexity for convolutional architectures, and the one for standard (fully connected) architectures. This result differs from ours in several aspects. Most importantly, we study the risk for estimating general invariant functions using invariant kernels and random features, while [LZA20] obtain results for a specific distribution using CNNs. Also, the weight sharing structure in [LZA20] is different from the one in Eq. (1).

Another work [CDL20] studied the statistical benefits of data augmentation in the parametric setting via a group theory framework. Our result is different in the sense that we consider the non-parametric setting to estimate an invariant function using kernel methods.

To the best of the our knowledge, our paper is the first that characterizes the precise statistical benefit of using invariant random features and kernel models.

Convolutional neural networks and convolutional kernels

A recent line of work [JGH18, LL18, DZPS19, DLL+18, AZLS19, AZLL18, ADH+19a, ZCZG18, OS19] studied the training dynamics of overparametrized neural networks under certain random initialization, and showed that it converges to a kernel estimator, which corresponds to the “neural tangent kernel”. The convolutional neural tangent kernel, which corresponds to the tangent kernel of convolutional neural networks, was studied in [ADH+19b, LWY+19, BM19]. The connection between convolutional kernel ridge regression and data augmentation was pointed out in [LWY+19].

The network in Eq. (1) corresponds to a two-layer convolutional neural network with global average pooling, which is a special case of the convolutional network that was defined as in [ADH+19b].

A number of authors have studied the generalization error of kernel machines [CDV07, JŞS+20, LR+20, LRZ19] [Wai19, Theorem 13.17] and random features models [RR09, RR17, MWW+20, Bac15]. However, these results are not fine-grained enough to characterize the separation between invariant kernels (or random feature models) and standard inner product kernels, for several reasons. First, some of these results concern restricted target functions with bounded RKHS norm. Second, we establish a gap that holds pointwise, i.e. for any given target function $f_{*}$, while most of earlier work only obtain minimax lower bounds. Finally, we need the upper and lower bounds match up to a $1+o_{d}(1)$ factor, while earlier results only match up to unspecified constants.

The recent paper [JŞS+20] provides sharp predictions for kernel machines, but it assumes that a certain random kernel matrix behaves like a random matrix with Gaussian components: proving an equivalence of this type is the central mathematical challenge we face here.

Our analysis builds on the general results of [GMMM19, MMM21]. In particular, [MMM21] provides general conditions under which the risk of random features and kernel methods can be characterized precisely. Checking these conditions for invariant methods requires to prove certain concentration properties for the entries of the relevant kernels. We achieve this goal for the cyclic group with general activations, and for degeneracy-$\alpha$ groups (for $\alpha\leq 1$) with polynomial activations. Generalizing these results to other groups, data distributions, and activations is a promising direction.

Examples

In this section, we provide three examples of our general setting. We show in Appendix D that all these groups have degeneracy 1 and therefore satisfy the assumptions of our general theorems.

We will refer to the invariant functions $L^{2}(\mathcal{A}_{d},{\rm Cyc}_{d})$ as the ‘cyclic functions’.

Suppose we have one-dimensional signals with very high resolution, but the signals are band-limited: their Fourier transforms have only $d$ non-zero coefficients. We assume that the labels of the band-limited signals are invariant under translations. The following model captures this setting.

That means, ${\rm Sft}_{d}$ can be interpreted as a subgroup of ${\mathcal{O}}(d)$. The measure $\pi_{d}$ is the uniform distribution on ${\rm Sft}_{d}$, i.e.,

Invariant random feature models

Let ${\mathcal{G}}_{d}$ be a group of degeneracy $\alpha$ with $\alpha\leq 1$ as defined in Definition 1 and $f_{d}$ be a function that is invariant under the action of ${\mathcal{G}}_{d}$, i.e., $f_{d}\in L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})$. We consider fitting the data with the invariant random features model defined in Eq. (2) using ridge regression, which we call invariant RFRR. Namely, we learn a function $\hat{f}^{{\rm inv}}_{N,\lambda}({\bm{x}};\hat{\bm{a}}(\lambda))=\sum_{1\leq j\leq N}\hat{a}_{j}\int_{{\mathcal{G}}_{d}}\sigma(\langle{\bm{w}}_{j},g\cdot{\bm{x}}\rangle)\pi_{d}({\rm d}g)$ with

where the regularization parameter $\lambda$ can depend on the dimension $d$. (The factor $d^{\alpha}$ in the ridge penalty is introduced to compensate for the effect of averaging the random features over ${\mathcal{G}}_{d}$.) We further denote the test error of invariant RFRR by

We will make the following assumption on $\sigma$.

For general $(\mathcal{A}_{d},{\mathcal{G}}_{d})$, we assume that $\sigma$ is a (finite degree) polynomial function.

We assume that $\sigma$ is not a polynomial with degree less or equal to $\max({\mathsf{s}},{\mathsf{S}})$.

Let ${\mathcal{G}}_{d}$ be a group of degeneracy $\alpha\leq 1$ and let $\{f_{d}\in L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})\}_{d\geq 1}$ be a sequence of ${\mathcal{G}}_{d}$-invariant functions. Assume $d^{{\mathsf{s}}-\alpha+\delta}\leq n\leq d^{{\mathsf{s}}+1-\alpha-\delta}$ and $d^{{\mathsf{S}}-\alpha+\delta}\leq N\leq d^{{\mathsf{S}}+1-\alpha-\delta}$ for fixed integers ${\mathsf{s}}$, ${\mathsf{S}}$ and some $\delta>0$. Let $\sigma$ be an activation function that satisfies Assumption 1 at level $({\mathsf{s}},{\mathsf{S}})$. Then the following hold for the test error of invariant RFRR (see Eq. (7)):

(Overparametrized regime) Assume $N\geq nd^{\delta}$ for some $\delta>0$. Then for any regularization parameter $\lambda=O_{d}(1)$ (including $\lambda=0$) and $\eta>0$, we have

(Underparametrized regime) Assume $n\geq Nd^{\delta}$ for some $\delta>0$. Then for any regularization parameter $\lambda=O_{d}(n/N)$ (including $\lambda=0$) and any $\eta>0$, we have,

In particular, this theorem applies to the one-dimensional and two-dimensional cyclic groups, and band-limited functions listed in Section 2. We refer readers to Appendix A.2 for an informal intuition and Appendix B.2 for the proof of this result.

We can compare these bounds with ridge regression on the standard random features model of Eq. (5). Theorem 2 in [MMM21] (with Assumption 1) shows that the same test error holds as in Theorem 1 but with $d^{{\mathsf{s}}+\delta}\leq n\leq d^{{\mathsf{s}}+1-\delta}$ and $d^{{\mathsf{S}}+\delta}\leq N\leq d^{{\mathsf{S}}+1-\delta}$. We thus gain a factor $d^{\alpha}$ in the sample and feature complexity by using invariant features compared to non invariant ones.

Assumption 1 requires the activation function to be polynomial, except for the cyclic group, for which only differentiability conditions are assumed. We believe that the differentiability condition (and indeed weaker conditions) should be sufficient for general groups. We defer these improvements to future work.

Consider two-dimensional images with $d=D\times D$ (Example 2) and functions $f_{d}$ that are invariant with respect to the group of cyclic translations along the horizontal direction only. It can be shown that this group has degeneracy $\alpha=1/2$, and in fact $\dim(V_{d,k}/V_{d,k}({\mathcal{G}}_{d}))\asymp D=d^{1/2}$. Our theory also applies to this group.

Invariant kernel machines

Note that any invariant kernel of the form (4) can be written as a kernel of the form:

To see this, note that any inner product kernel $h$ can be decomposed as

for some activation function $\sigma$, which amounts to taking the square root of the positive semidefinite operator associated to $h$. Substituting in Eq. (4), we get the desired representation.

Consider Kernel ridge regression with regularization parameter $\lambda$ associated to $H_{d,{\rm inv}}$, that we call invariant KRR. Namely, we learn a function $\hat{f}_{\lambda}^{\rm inv}({\bm{x}};\hat{\bm{u}}(\lambda))=\sum_{i\in[n]}\hat{u}_{i}H_{d,{\rm inv}}({\bm{x}}_{i},{\bm{x}})$ where

with $\|\cdot\|_{\mathcal{H}}$ the RKHS norm associated to $H_{d,{\rm inv}}$. We further denote the test error of invariant KRR by

Let ${\mathcal{G}}_{d}$ be a group of degeneracy $\alpha\leq 1$ and $\{f_{d}\in L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})\}_{d\geq 1}$ be a sequence of ${\mathcal{G}}_{d}$-invariant functions. Assume $d^{{\mathsf{s}}-\alpha+\delta}\leq n\leq d^{{\mathsf{s}}+1-\alpha-\delta}$ for some fixed integer ${\mathsf{s}}\geq 1$ and some $\delta>0$. Let $\sigma$ be an activation function that satisfies Assumption 1 at level $({\mathsf{s}},{\mathsf{s}})$ (and $N=\infty$) and let $H_{d,{\rm inv}}$ be the associated invariant kernel as defined in Eq. (10). Then, the following holds for the test error of invariant KRR (c.f. Eq. (12)): for any $\lambda=O_{d}(1)$ (including $\lambda=0$ identically) any $\eta>0$, we have

We can compare the performance of this kernel against a standard (inner product) kernel $H_{d}({\bm{x}},{\bm{y}})=h_{d}(\langle{\bm{x}},{\bm{y}}\rangle/d)$. Then Theorem 4 in [GMMM19] shows that the above theorem holds but with $d^{{\mathsf{s}}+\delta}\leq n\leq d^{{\mathsf{s}}+1-\delta}$. We gain a factor $d^{\alpha}$ in sample complexity by using an invariant kernel.

Recall that the neural tangent kernel (NTK) associated to a function $f({\bm{x}};{\bm{\Theta}})$ with random initialization ${\bm{\Theta}}_{0}$ is defined as

The neural tangent kernel associated to a multi-layers fully connected network is an inner-product kernel (as long as the weights are initialized to be isotropic Gaussian.) In contrast, the NTK associated to the CNN of Eq. (1) is an example of invariant kernel, and is covered by Theorem 2 (see Appendix A.3 for more details).

Comparison with alternative approaches

To provide further context, it is useful to compare invariant random features and kernel models with other approaches. Here we consider two alternatives: $(i)$ output symmetrization, which uses a non-invariant method for training and then symmetrizes the estimated function over the group ${\mathcal{G}}_{d}$ to obtain an invariant function; $(ii)$ data augmentation, which trains the model on a dataset augmented by samples obtained by applying group transformations to the original data. As shown in [LWY+19], data augmentation is mathematically equivalent to invariant kernel methods, so that it is superior to standard kernel methods (with inner-product kernels). On the other hand, we show that output symmetrization of standard kernel estimators does not significantly improve over the standard kernel estimator, and is fundamentally sub-optimal comparing to invariant kernel methods.

Given an estimater $\hat{f}$, the symmetrization operator ${\mathcal{S}}\hat{f}$ computes the average of $\hat{f}$ over the group:

When the target function $f_{d}$ is ${\mathcal{G}}_{d}$-invariant, one might naively think that the symmetrization operation will significantly improve the performance of standard kernel estimators (standard RFRR and KRR). Indeed, when $f_{d}\in L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})$, Jensen’s inequality gives $\|f_{d}-{\mathcal{S}}\hat{f}\|_{L^{2}}^{2}=\|{\mathcal{S}}(f_{d}-\hat{f})\|_{L^{2}}^{2}\leq\|f_{d}-\hat{f}\|_{L^{2}}^{2}$. However, the proposition below (which is proved in Section A.4) shows that ${\mathcal{S}}\hat{f}$ is not significantly better when $\hat{f}$ is a standard kernel estimator.

while Theorem 1 implies that invariant RFRR $\hat{f}_{{\rm RF}}^{\rm inv}$ with sufficiently small regularization achieves a substantially smaller risk:

2 Data augmentation

We consider full data augmentation whereby we replace each sample $(y_{i},{\bm{x}}_{i})$ in the dataset by $|{\mathcal{G}}_{d}|$ samples $\{(y_{i},g\cdot{\bm{x}}_{i}):g\in{\mathcal{G}}_{d}\}$ (for simplicity we consider here the case of a finite group ${\mathcal{G}}_{d}$), and perform standard KRR on the augmented dataset. One might naively think that this is not as effective as enforcing invariance in the kernel structure. After all, we are only requiring invariance to hold at the sampled points. However, [LWY+19] showed that these two approaches are in fact equivalent.

We compare KRR using the kernel $H({\bm{x}},{\bm{y}})=h(\langle{\bm{x}},{\bm{y}}\rangle/d)$ on the augmented dataset, with invariant KRR on the original dataset using the symmetrized kernel $H_{{\rm inv}}({\bm{x}},{\bm{y}})=\int_{{\mathcal{G}}_{d}}h(\langle{\bm{x}},g\cdot{\bm{y}}\rangle/d)\pi_{d}({\rm d}g)$. Denote by $\hat{f}_{\lambda}^{{\rm data}}$ and $\hat{f}_{\lambda}^{{\rm inv}}$ the KRR estimates with the standard kernel $H$ and full data augmentation, and with the invariant kernel $H_{\rm inv}$ respectively.

Let ${\mathcal{G}}$ be a finite group, and $H$, $H_{\rm inv}$ as defined above. Then we have $\hat{f}_{\lambda}^{{\rm data}}=\hat{f}_{\lambda}^{{\rm inv}}$.

A couple of remarks are in order. First, this equivalence is general (holds for any dataset $\{(y_{i},{\bm{x}}_{i})\}_{i\leq n}$), and is in fact a consequence of the algebraic structure of ridge regressions. Second, while this result establishes that the two approaches are mathematically equivalent, there are computational advantages for invariant KRR. Indeed, full data augmentation increases the size of the kernel matrix from $n$ to $n|{\mathcal{G}}_{d}|$ which is computationally more expensive. Finally, this equivalence shows that data augmentation with standard KRR is superior to output symmetrization of standard KRR.

Numerical illustration

where the sub-index $i$ in $x_{i}$ should be understood in the modulo $d$ sense ($d+1=1~{}({\rm mod}~{}d)$). We compare the performance between two kernels: a standard (inner product) kernel $H_{d}({\bm{x}},{\bm{y}}):=h_{d}(\langle{\bm{x}},{\bm{y}}\rangle/d)$ that we take to be the neural tangent kernel associated to a depth-$5$ neural network with fully connected layers and ReLu activations $\sigma(x)=\max(x,0)$. We compare this with its cyclically invariant counterpart

where $g_{i}\in{\rm Cyc}_{d}$ is the shift by $i$ positions as defined in Example 1. Note that the precise number of layers $L$ is not important. As long as $L$ is fixed in the large $N,n$ limit, our predictions remain unchanged, and the simulations appear to confirm this.

In Figure 1, we report the test errors of fitting each cyclic polynomials with KRR with the two kernels, and regularization parameter $\lambda=0^{+}$ (min-norm interpolation). We consider $\sigma_{\varepsilon}=0$ and we report the risk averaged over 10 instances against the number of samples $n$. We observe that the risk in fitting $f_{d,{\rm lin}}$, $f_{d,{\rm quad}}$ and $f_{d,{\rm cube}}$, using KRR with the cylcic kernel $H_{d,{\rm Cyc}}$ drops when $n=\Theta_{d}(1)$, $n=\Theta_{d}(d)$ and $n=\Theta_{d}(d^{2})$ respectively. In contrast, the risk of KRR with the standard kernel drops when $n=\Theta_{d}(d)$, $n=\Theta_{d}(d^{2})$ and $n=\Theta_{d}(d^{3})$ respectively. This matches well the predictions of Theorem 2.

We next investigate the relevance of our results for real data. We consider the MNIST dataset ($d=28\times 28=784$, $n_{{\rm train}}=60000$, $n_{{\rm test}}=10000$ and $10$ classes). We encoded class labels by $y_{i}\in\{-4.5,-3.5,\ldots,3.5,4.5\}$. We make these data invariant under cyclic translations in two dimensions (Example 2): for each samples in the training and test sets, we replace the image by a uniformly generated 2 dimensional (cyclic) translation of the image (see Fig. 5 in Appendix A.5.2). In this cyclic invariant MNIST data set, the labels are therefore invariant under the action of ${\rm Cyc2D}_{28,28}$.

In order to explore the role of data anisotropy, we pre-process images as follows. We compute the discrete Fourier transform components of the images in the training set and select the $T\in\{20,70,120,200,400,784\}$ components with the highest average absolute value. For each $T$, we then construct training and test sets in which we project each image onto the top $T$ frequencies (see Fig. 3 in Appendix A.5.2). When $T$ is small, we expect all the non-zero frequencies to have comparable variance and therefore $d_{\mbox{\tiny\rm eff}}\approx T$. For larger $T$, we include frequencies of progressively small variance, and therefore $d_{\mbox{\tiny\rm eff}}$ should saturate.

For each frequency content $T$, we compare the performance of two kernels: a standard inner-product kernel $H_{d}({\bm{x}},{\bm{y}}):=h_{d}(\langle{\bm{x}},{\bm{y}}\rangle/d)$ and its cyclic counterpart given by

where $g_{ij}\in{\rm Cyc2D}_{28,28}$. We choose $H_{d}$ to be the neural tangent kernel associated to a two-layers neural network, and hence $H_{d,{\rm Cyc}}$ is the one associated to a CNN analogous to (1) (but in two dimensions). We compute the KRR estimates with regularization parameter $\lambda=0^{+}$. In Fig. 2, we report the classification error averaged over 5 instances against the number of samples $\log(n)/\log(d)$.

We observe that the cyclic invariant kernel vastly outperform the inner product kernel: the same test error is achieved at a significantly smaller sample size, in qualitative agreement with our general theory. In order to quantify this gap, for each $T$ we fit two curves to the test error of the two kernels, which differ uniquely in an horizontal shift (see Appendix A.5.2). We estimate the sample complexity gain by the difference between these shifts, and denote this estimate by $d_{\mbox{\tiny\rm eff}}$.

It is visually clear that $d_{\mbox{\tiny\rm eff}}$ increases with $T$, as expected. We plot $d_{\mbox{\tiny\rm eff}}$ as a function of $T$ in Fig. 6 in Appendix A.5.2. We observe that the behavior of $d_{\mbox{\tiny\rm eff}}$ roughly matches our expectations: it grows linearly at small $T$ and eventually saturates.

Acknowledgments

This work was supported by NSF through award DMS-2031883 and from the Simons Foundation through Award 814639 for the Collaboration on the Theoretical Foundations of Deep Learning We also acknowledge NSF grants CCF-2006489, IIS-1741162 and the ONR grant N00014-18-1-2729.

References

Appendix A Some details in the main text

In the proposition below, we show that the approximation power of two-layers ${\mathcal{G}}_{d}$-invariant neural networks are always no worse than two-layers fully-connected neural networks when the target function is ${\mathcal{G}}_{d}$-invariant.

We define the symmetrization operator ${\mathcal{S}}:L^{2}(\mathcal{A}_{d})\to L^{2}(\mathcal{A}_{d};{\mathcal{G}}_{d})$ by

Since $f_{*}\in L^{2}(\mathcal{A}_{d};{\mathcal{G}}_{d})$, by Jensen’s inequality, for any $f\in L^{2}(\mathcal{A}_{d})$, we have

Moreover, for any $f\in{\mathcal{F}}_{{\sf NN},N}$, we have ${\mathcal{S}}f\in{\mathcal{F}}_{{\sf NN},{\mathcal{G}}_{d},N}$. This gives

A.2 Intuition for the proofs of Theorems 1 and 2

Theorem 1 and 2 are consequences of general theorems proved in [MMM21]. The $d^{\alpha}$ improvement between invariant and non-invariant models can be understood as follows: consider an inner-product activation $\sigma(\langle{\bm{x}},{\bm{\theta}}\rangle/\sqrt{d})$ with ${\bm{x}},{\bm{\theta}}\sim{\rm Unif}(\mathcal{A}_{d})$ (where we denoted ${\bm{\theta}}=\sqrt{d}\cdot{\bm{w}}$), then we have the following eigendecomposition

where $\{Y^{(d)}_{kl}\}_{l\in[B(\mathcal{A}_{d};k)]}$ form an orthonormal basis of $V_{d,k}$, the subspace of degree-$k$ polynomials on $\mathcal{A}_{d}$ (see Section H for background on functional spaces on the sphere and hypercube). The eigenvalues of $\sigma$ are given by $\{\xi_{d,k}\}_{k\geq 0}$ with each having degeneracy $B(\mathcal{A}_{d};k)$.

As mentioned in the introduction, the symmetry group ${\mathcal{G}}_{d}$ preserves $V_{d,k}$ (see Section C.2) and the invariant activation function has the following eigendecomposition

where the $\{\overline{Y}^{(d)}_{kl}\}_{l\in[B(\mathcal{A}_{d};k)]}$ form an orthonormal basis of $V_{d,k}({\mathcal{G}}_{d})$, the subspace of degree-$k$ invariant polynomials on $\mathcal{A}_{d}$. The eigenvalues of $\overline{\sigma}$ are given by $\{\xi_{d,k}\}_{k\geq 0}$ with each having degeneracy $D(\mathcal{A}_{d};k)$.

Hence $\overline{\sigma}$ has the same eigenvalues $\xi_{d,k}$ as $\sigma$, but with degeneracy smaller by a factor

This intuition is verified rigorously in the proof of these theorems in Appendix B.

A.3 Convolutional neural tangent kernel

By the technical backgrounds in Section H, we can see that $h_{d}^{(1)}$ and $h_{d}^{(2)}$ can be well-defined.

Calculating the derivative of the neural network with respect to ${\bm{a}}=(a_{1},\ldots,a_{N})$, we have

Since ${\mathcal{G}}_{d}$ is a discrete group, by law of large numbers, we have

Moreover, calculating the derivative of the neural network with respect to ${\bm{W}}=({\bm{w}}_{1},\ldots,{\bm{w}}_{N})$, we have

Since ${\mathcal{G}}_{d}$ is a discrete group, by law of large numbers, we have

Taking $h_{d}=h_{d}^{(1)}+h_{d}^{(2)}$ concludes the proof. ∎

A.4 Proof of Proposition 1

Let $\hat{f}_{d}$ be an estimator satisfying

By Jensen’s inequality and by the equation above, we have

A.5 Details of numerical simulations

We consider the standard (inner-product) kernel $H_{d}({\bm{x}},{\bm{y}})=h_{{\rm NTK}}(\langle{\bm{x}},{\bm{y}}\rangle/d)$ to be the neural tangent kernel associated to a depth-$5$ neural network with fully connected layers and ReLu activation $\sigma(x)=\max(x,0)$. This can be obtained iteratively as follow (see [JGH18] and [BB20]): define for $u\in$,

and $h_{{\rm NTK}}(u)=h_{{\rm NTK}}^{5}(u)$ with $h^{1}_{{\rm NTK}}(u)=h^{1}(u)=u$ and for $k=2,\ldots,5$,

We compute the cyclic invariant kernel by summing over all cyclic translations $g\in{\rm Cyc}_{d}$:

A.5.2 Cyclic invariant MNIST data set

We consider the MNIST data set of $28\times 28$ grayscale images ($d=784$) of handwritten digits, which contains $60000$ training images and $10000$ testing images. We pre-process the images in three steps:

We compute the discrete Fourier transform of the images in the training set and compute the average absolute value of the frequency components (see left frame of Fig. 3). For each $T\in\{20,70,120,200,400,784\}$, we select $\Omega_{T}\subset\times$ to be the set of the top $T$ frequencies (i.e., the $T$ frequencies with highest absolute value averaged on the training set).

For each $T$, we construct a train and test sets in which we project each image onto $\Omega_{T}$ (i.e., we set all the frequency components not in $\Omega_{T}$ to ). We displayed in Fig. 4 two digits and their projection on the top $T$ frequencies $\Omega_{T}$ for different $T$.

For each image in the training and test sets, we replace the image by a uniformly generated 2 dimensional (cyclic) translation of the image. We display some examples in Fig. 5.

We further normalize the images so that $\|{\bm{x}}\|_{2}=1$ and center the labels $y_{i}\in\mathcal{Y}$ where $\mathcal{Y}=\{-4.5,-3.5,\ldots,3.5,4.5\}$. In order to compute the classification error, we round the prediction value to the nearest label in $\mathcal{Y}$.

We use the inner-product kernel $H_{d}({\bm{x}},{\bm{y}})=h_{{\rm NTK}}(\langle{\bm{x}},{\bm{y}}\rangle/d)$ where $h_{{\rm NTK}}$ is the neural tangent kernel associated to a 2-layers neural network with fully connected layers and ReLu activation $\sigma(x)=\max(x,0)$, which given by

The cyclic invariant kernel is computed by summing over all two-dimensional cyclic translations $g_{ij}\in{\rm Cyc2D}_{28,28}$:

For each $T$, we estimate the effective dimension $d_{\mbox{\tiny\rm eff}}$ by fitting two parallel lines through the classification error points of the standard and cyclic kernels at the same time (keeping only the points where the curves decrease). The estimated (log) effective dimension is then given by the difference of the offsets. We report these estimates for different $T$ in Fig. 6.

Appendix B Proof of the main theorems

In this section, we present the proofs of Theorem 1 and 2 stated in the main text. The rest of the appendices are organized as follow:

Appendix C presents key properties of the decomposition of invariant functions, while Appendix H reviews some technical background on the functional spaces on the sphere and the hypercube.

Appendix D proves that the examples of symmetry group listed in Section 2 (one and two-dimensional cyclic groups and band-limited functions) have degeneracy 1.

Appendix E presents a key concentration result on the diagonal elements of polynomial invariant kernels. In particular, the results of Appendix E are the only ones required in the proofs of Theorems 1 and 2 in the case of polynomial activations for general symmetry group ${\mathcal{G}}_{d}$ of degeneracy $\alpha\leq 1$.

B.2 Proof of Theorem 1

Let ${\mathcal{G}}_{d}$ be a group of degeneracy $\alpha\leq 1$. Consider ${\bm{x}},{\bm{\theta}}\sim{\rm Unif}(\mathcal{A}_{d})$, $d^{{\mathsf{s}}-\alpha+\delta_{0}}\leq n\leq d^{{\mathsf{s}}-\alpha+1-\delta_{0}}$, $d^{{\mathsf{S}}-\alpha+\delta_{0}}\leq N\leq d^{{\mathsf{S}}-\alpha+1-\delta_{0}}$ and an activation function $\sigma$ that satisfies Assumption 1 at level $({\mathsf{s}},{\mathsf{S}})$. Denote

Theorem 1 is a consequence of Theorem 1 in [MMM21] where we take ${\mathcal{X}}_{d}=\Omega_{d}=\mathcal{A}_{d}$, $\nu_{d}=\tau_{d}={\rm Unif}(\mathcal{A}_{d})$ and ${\mathcal{D}}_{d}={\mathcal{V}}_{d}=L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})\subset L^{2}(\mathcal{A}_{d})$. The proof amounts to checking that $\overline{\sigma}$ indeed verifies the feature map concentration and spectral gap assumptions (see Section 2.2 in [MMM21]). We borrow some of the notations introduced in [MMM21] and refer the reader to their Section 2.1.

For the sake of simplicity, we consider the overparametrized case $N(d)\geq n(d)d^{\delta}$ for some $\delta>0$, and therefore ${\mathsf{S}}\geq{\mathsf{s}}$. The underparametrized case $d^{\delta}N(d)\leq n(d)$ is treated analogously.

Step 1. Diagonalization of the activation function $\overline{\sigma}$ and choosing ${\mathsf{m}}={\mathsf{m}}(d)$, ${\mathsf{M}}={\mathsf{M}}(d)$.

We can decompose the inner product activation $\sigma$ in the basis of Gegenbauer polynomials (see Section H for definitions):

where (with ${\bm{e}}\in\mathcal{A}_{d}$ arbitrary)

From Assumption 1.$(a)$ that $|\sigma(x)|\leq c_{0}\exp(c_{1}x^{2}/2)$ for some constants $c_{0}>0$ and $c_{1}<1$ (which is trivially verified for a polynomial activation function), there exists a constant $C>0$ such that (see for example Lemma 5 in [GMMM19])

From the correspondence between Gegenbauer and Hermite polynomials when $d\to\infty$ (see Eq. (111) in Section H.1.3), Assumption 1.$(b)$ implies that $\xi_{d,k}^{2}=\Theta_{d}(d^{-k})$ for $k=0,\ldots,{\mathsf{s}}$.

Denote $(\lambda_{d,j})_{j\geq 1}$ the eigenvalues of $\overline{\sigma}$ in non increasing order of their absolute value (namely, the $\xi_{d,k}$’s which have degeneracies $D(\mathcal{A}_{d};k)$). Set ${\mathsf{m}}$ and ${\mathsf{M}}$ to be the number of eigenvalues $\lambda_{d,j}^{2}$ that are bigger than $d^{-{\mathsf{s}}-1+\delta}$ and $d^{-{\mathsf{S}}-1+\delta}$ respectively, for a constant $\delta>0$ that will be set sufficiently small (see Step 4). From the above discussion, $(\lambda_{d,j})_{j\leq{\mathsf{m}}}$ corresponds exactly to all the eigenvalues associated to invariant polynomials of degree less of equal to ${\mathsf{s}}$, while $(\lambda_{d,j})_{j\leq{\mathsf{M}}}$ does not contain any eigenvalues associated to invariant polynomials of degree bigger or equal to ${\mathsf{S}}+1$. Hence,

where we used that ${\mathcal{G}}_{d}$ has degeneracy $\alpha$ so that $D(\mathcal{A}_{d};k)=\Theta_{d}(d^{-\alpha})\cdot B(\mathcal{A}_{d};k)$.

Step 2. Diagonal elements of the truncated kernel.

We introduce the kernel associated to activation $\overline{\sigma}$:

Similarly, we introduce a kernel in the feature space

The diagonal elements of the truncated kernels are then given by

Step 3. Checking the feature map concentration property at level $\{N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d)\}_{d\geq 1}$.

Let us first consider the case of a polynomial activation function $\sigma$. Denote $D$ its degree and $u=u(d)$ the total (finite) number of nonzero eigenvalues of $\overline{\sigma}$ (which are associated to invariant polynomials of degree less or equal to $D$). Let us verify the feature map concentration property (Assumption 1 in [MMM21]) with sequence $u(d)\geq\max({\mathsf{m}},{\mathsf{M}})$. Note that $u\geq\max({\mathsf{m}},{\mathsf{M}})$, part $(b)$ and $(c)$ of the property are trivially verified in that case.

(Hypercontractivity of finite eigenspaces on ${\mathcal{D}}_{d}$.) The subspace of polynomials of degree less or equal to $D$ on the hypercube and the sphere verifies the hypercontractivity property (see Lemmas 18 and 19 in Section H.3).

(Concentration of diagonal elements.) From Eq. (27) and Proposition 7 stated in Section E, we have

A similar computation shows the concentration of the diagonal elements of $U_{d,>{\mathsf{M}}}$.

(Hypercontractivity of the high degree part.) Denote $\overline{\sigma}_{>u}={\overline{\mathsf{P}}}_{E}\overline{\sigma}$ the activation $\overline{\sigma}$ obtained by setting the first $u$ eigenvalues to (i.e., setting coefficients $k\not\in E$ to zero in Eq. (25)). From Eq. (28), we need to show that for $p$ as defined in Assumption 1.$(a)$, we have

Using hypercontractivity of polynomials of degree less or equal to $4p$, the first term is bounded by $O_{d}(d^{-1/2})$, while the second term is bounded in Proposition 10 in Section G.

(Concentration of diagonal elements.) This is proved in Proposition 8 in Section F.

Step 4. Checking the spectral gap property at level $\{N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d)\}_{d\geq 1}$.

Let us now check the spectral gap property (Assumption 2 in [MMM21]).

(Number of samples.) First by Eq. (26) and the assumption $d^{{\mathsf{s}}-\alpha+\delta_{0}}\leq n\leq d^{{\mathsf{s}}+1-\alpha-\delta_{0}}$, we have ${\mathsf{m}}\leq n^{1-\delta}$ for $\delta>0$ chosen sufficiently small. By the choice of ${\mathsf{m}}$ and recalling Eq. (28), we have

with $\delta>0$ chosen sufficiently small.

(Number of features.) By construction ${\mathsf{M}}\geq{\mathsf{m}}$. Furthermore, recalling Eq. (26) and the assumption $d^{{\mathsf{S}}-\alpha+\delta_{0}}\leq N\leq d^{{\mathsf{S}}+1-\alpha-\delta_{0}}$, we have ${\mathsf{M}}\leq N^{1-\delta}$ for $\delta>0$ chosen sufficiently small. By choice of ${\mathsf{M}}$, $\lambda_{d,{\mathsf{M}}+1}^{2}\leq d^{-{\mathsf{S}}-1+\delta}$. Hence,

for $\delta>0$ chosen sufficiently small.

B.3 Proof of Theorem 2

We consider the same setting as in the previous section and consider

Theorem 2 is a consequence of Theorem 4 in [MMM21] and the proof amounts to checking that $H_{d}$ verifies the kernel concentration properties and eigenvalue condition (see Section 3.2 in [MMM21]). Note that some of the conditions were already covered in the proof of Theorem 1 and we will only mention the ones that still need to be verified. Furthermore, by the spectral gap property proven in Section B.2, the bound in Theorem 4 in [MMM21] (which is in term of a shrinkage operator) can indeed be rewritten as

We choose ${\mathsf{m}}$ as in the proof of Theorem 1.

Step 1. Checking the kernel concentration property at level $\{n(d),{\mathsf{m}}(d)\}_{d\geq 1}$.

and the concentration of the diagonal elements in the case of a polynomial activation function follows from the same argument as in Section B.2.

(Concentration of the diagonal elements of the kernel.) This is proven in Proposition 9 in Section F.

Step 2. Checking the eigenvalue condition at level $\{n(d),{\mathsf{m}}(d)\}_{d\geq 1}$.

Appendix C Decomposition of invariant functions

Let $L^{2}(\mathcal{A}_{d})$ be the class of $L^{2}$ functions on $\mathcal{A}_{d}$ equipped with uniform probability measure ${\rm Unif}(\mathcal{A}_{d})$. We define the invariant function class to be

We define the symmetrization operator ${\mathcal{S}}:L^{2}(\mathcal{A}_{d})\to L^{2}(\mathcal{A}_{d},{\mathcal{G}}_{d})$ to be

C.2 Orthogonal polynomials on invariant function class

We denote $D(\mathcal{A}_{d};k)=D(\mathcal{A}_{d};{\mathcal{G}}_{d};k)\equiv\dim({\mathcal{P}}_{k}(\mathcal{A}_{d},{\mathcal{G}}_{d}))$ to be the dimension of ${\mathcal{P}}_{k}(\mathcal{A}_{d},{\mathcal{G}}_{d})$. We denote $\{\overline{Y}_{kl}^{(d)}\}_{l\in[D(\mathcal{A}_{d};k)]}$ to be a set of orthonormal polynomial basis in ${\mathcal{P}}_{k}(\mathcal{A}_{d},{\mathcal{G}}_{d})$. That means

C.3 A representation lemma

We have the following representation lemma. This lemma is important in the proofs of counting the degeneracy of groups (See Section D).

Let $Q_{k}^{(d)}$ be the $k$-th Gegenbauer polynomial, or the $k$-th hypercubic Gegenbauer polynomial. For any fixed integer $k$, we have

Recall that $Q_{k}^{(d)}$ is a representation of the projector onto the subspace of degree-$k$ spherical harmonics (see Eq. (104) in Section H.1.2). We deduce that

C.4 Gegenbauer decomposition of invariant features and kernels

so that we have the following equation holds in $L^{2}([-\sqrt{d},\sqrt{d}],\tau^{1}_{d})$ sense

For any group ${\mathcal{G}}_{d}$ that is a subgroup of ${\mathcal{O}}(d)$, we define

Then, by the representation lemma (Lemma 1), we have

Appendix D Counting the degeneracy

Here we state a key lemma that is used to prove Proposition 5.

Let ${\mathcal{G}}_{d}\in\{{\rm Cyc}_{d},{\rm Cyc2D}_{d_{1},d_{2}}\}$ with $d=d_{1}\times d_{2}$. Denote

We prove Eq. (31) and (33). The proof for Eq. (32) is similar to the proof of Eq. (31).

Note that for either ${\mathcal{G}}_{d}\in\{{\rm Cyc}_{d},{\rm Cyc2D}_{d_{1},d_{2}}\}$, for any $i\in[d]$ and $1\leq l\leq d-1$, the random variable $(L_{l}{\bm{x}})_{i}$ is independent from $x_{i}$. This gives

Step 3. The case $k\geq 3$. By the moment formula of the $\chi^{2}$ distribution, we have

Moreover, for either ${\mathcal{G}}_{d}\in\{{\rm Cyc}_{d},{\rm Cyc2D}_{d_{1},d_{2}}\}$, for any $l\neq 0$, we have

As a consequence, by the Hanson-Wright inequality as in Lemma 3, for any fixed $k\geq 3$ and $\varepsilon>0$, we have

Combining Eq. (34), (35), and (36) proves Eq. (31).

Note that for fixed $k\geq 1$, the moment formula for $\chi^{2}$ distribution gives

By Lemma 1, for any fixed $k\geq 1$, we have

where $|a_{d,k,m}|\leq C_{k,m}/d^{(k-m)/2}$. As a result, we have

Combining with Eq. (37) shows that $D(\mathcal{A}_{d};k)=\Theta(d^{-1}B(\mathcal{A}_{d};k))=\Theta(d^{k-1})$. This concludes the proof. ∎

D.1.2 Auxiliary lemmas

Note that for any permutation matrix $L$, we have $\|L\|_{F}\leq\sqrt{d}$, and $\|L\|_{{\rm op}}\leq 1$. By the Hanson-Wright inequality of vectors with independent sub-Gaussian entries (for example, see Theorem 1.1 of [RV+13]), we have

Let $Q_{k}^{(d)}$ be either the $k$’th Gegenbauer polynomial or the $k$’th hypercubic Gegenbauer polynomial (as defined in Section H). Let coefficients of monomials in $Q_{k}^{(d)}(d\cdot x)$ to be $\{a_{d,k,m}\}_{0\leq m\leq k}$. That is, we have

Then, for any fixed $k$, there exists constant $C(k)$, such that

Finally, for $k$ and $m$ in different parity, we have

The proof holds by the following equation

when $Q_{k}^{(d)}$ is either Gegenbauer polynomial or Hypercubic Gegenbauer polynomial (See Eq. (110) and Eq. (112)). ∎

D.2 Counting the degeneracy of band-limited function class (Example 3)

Follow the notations of Example 3. Then for any fixed $k\geq 1$, we have

Here we state Lemma 5 that is used to prove Proposition 6. Given Lemma 5, the proof of Proposition 6 is the same as the proof of Proposition 5.

Follow the notations of Example 3. Denote

We prove the lemma for the case when $d$ is odd. We denote $u_{1}=z_{1}^{2}$, and $u_{i}=z_{2i}^{2}+z_{2i+1}^{2}$ for $i=2,\ldots,(d-1)/2$. Then we have

Step 1. Bound $Z$ function. First, we denote

Step 2. Bound $|{\mathcal{I}}|$. Further, we denote

Step 3. Bound $E$ function. Next, we denote

Moreover, for any $(j_{1},\ldots,j_{k})\not\in{\mathcal{I}}$, we have $E(j_{1},\ldots,j_{k})=0$. For any $(j_{1},\ldots,j_{k})\in{\mathcal{I}}$, we have

The last inequality used the fact that $(j_{1},\ldots,j_{k})\in{\mathcal{I}}$.

Step 4. Concludes the proof. Therefore, combining Eq. (38) (39) (41) (42), we have

Combining Eq. (38) (40) (41) (43), we have

Appendix E Concentration for invariant groups with degeneracy α≤1𝛼1\alpha\leq 1

In this section, we show that $\Upsilon_{k}$ concentration around its mean, for any fixed $k\geq 2$ and $\alpha\leq 1$.

Let ${\mathcal{G}}_{d}$ be an invariant group with degeneracy $\alpha\leq 1$. Let $({\bm{\theta}}_{i})_{i\in[N]}\sim{\rm Unif}(\mathcal{A}_{d})$ where $N=O_{d}(d^{p})$ for some fixed integer $p$. Let $\Upsilon_{k}$ be as defined in Eq. (44). Then for any fixed $k\geq 2$, we have

Let $\{a_{d,k,m}\}_{0\leq m\leq k}$ be the coefficients of monomials in $Q_{k}^{(d)}(d\cdot x)$. That is, we have

Moreover, by Lemma 4, we have $|a_{d,k,m}|\leq C_{k,m}/d^{(k-m)/2}$, $\lim_{d\to\infty}a_{d,k,k}=1$, and $a_{d,k,m}=0$ for $k$ and $m$ of different parity.

By the concentration of $\chi^{2}$-distribution, for any $\varepsilon>0$, the following event happens with high probability

Moreover, combining Lemma 6 with Lemma 7, for any fixed $m\geq 2$, we have

By the hypercontractivity property of Gaussian distribution as per Lemma 20, for any $\varepsilon>0$, taking $q$ sufficiently large, we have

By Markov’s inequality, we deduce that the following event happens with high probability

and by the hypercontractivity property of low degree polynomials with Gaussian measure (Lemma 20), for any $\varepsilon>0$, taking $q$ sufficiently large, we have

As a result, the following event happens with high probability

When all the events ${\mathcal{E}}_{1}$, ${\mathcal{E}}_{2}$, and ${\mathcal{E}}_{3}$ happen, for any $k\geq 2$, we have

The case of the hypercube $\mathcal{A}_{d}\sim{\mathscrsfs Q}^{d}$ follows similarly without introducing the gaussian measure and using Lemma 8 instead of Lemma 7. ∎

E.2 Auxiliary Lemmas

Let ${\mathcal{G}}_{d}$ be an invariant group with degeneracy $\alpha\leq 1$. Denote

Then for any fixed $s\in[1,\infty)$ and integer $k\geq 1$, we have

For ${\bm{\theta}}\in\mathcal{A}_{d}$, denote

By Lemma 1 and by the assumption that ${\mathcal{G}}_{d}$ is an invariant group with degeneracy $\alpha\leq 1$, i.e., $B(\mathcal{A}_{k};k)/[D(\mathcal{A}_{k};k)d^{\alpha}]=\Theta_{d}(1)$, for any fixed $k\geq 1$, we have

Throughout the proof, we will denote $L^{s}=L^{s}(\mathcal{A}_{d})$ to be the $L^{s}$ space with respect to distribution ${\bm{\theta}}\sim{\rm Unif}(\mathcal{A}_{d})$.

By the hypercontractivity of low degree polynomials on the sphere and the hypercube, as per Lemmas 18 and 19, for any $s\geq 1$, we have

Let $\{a_{d,k,m}\}_{0\leq m\leq k}$ be the coefficients of monomials in $Q_{k}^{(d)}(d\cdot x)$. That is, we have

Moreover, by Lemma 4, we have $|a_{d,k,m}|\leq C_{k,m}/d^{(k-m)/2}$, $\lim_{d\to\infty}a_{d,k,k}=1$, and $a_{d,k,m}=0$ for $k$ and $m$ have different parity.

We conclude the proof by induction over $k$. Note we have $F_{0}({\bm{\theta}})\equiv 1$. Moreover, for any $s\geq 1$, by Eq. (47) and (48) (and note that $a_{d,1,0}=0$ and $\lim_{d\to\infty}a_{d,1,1}\to 1$), we have

Fix a $k\geq 2$. Assume that, for any $1\leq u\leq k-1$, we have $\|F_{u}\|_{L^{s}}\leq C_{u}/d^{\alpha}$ for $s\geq 1$, by Eq. (48) and (47), and the fact that $|a_{d,k,m}|\leq C_{k,m}/d^{(k-m)/2}$ and $\lim_{d\to\infty}a_{d,k,k}=1$, we have

where we recall that we assume $\alpha\leq 1$.

by hypercontractivity of low degree polynomials for Gaussian measure (Lemma 20). ∎

Let ${\bm{x}}\sim{\sf N}({\bm{0}},{\mathbf{I}}_{d})$. Let ${\mathcal{G}}_{d}$ be a general invariant group. Let $F_{k}({\bm{z}})$ be defined as in Lemma 6. Then for any fixed $k\geq 1$, there exists a constant $C_{k}$, such that

By the Gaussian Poincaré inequality, we have

Case 1: Odd $k$. When $k$ is odd, we have

where we used in the second line Cauchy-Schwarz inequality and that the matrix representations of $g$ are orthogonal matrices, and in the last inequality the hypercontractivity of low degree polynomials for Gaussian measures (Lemma 20).

Case 2: Even $k$. Bound 1. When $k$ is even, we have the following first bound

Combining these two bounds yields the result for $k$ even. ∎

Let ${\bm{\theta}}\sim{\rm Unif}({\mathscrsfs Q}^{d})$. Let ${\mathcal{G}}_{d}$ be a general invariant group that preserves ${\mathscrsfs Q}^{d}$. Let $F_{k}({\bm{z}})$ be defined as in Lemma 6. Then for any fixed $k\geq 1$, there exists a constant $C_{k}$, such that

The proof is similar to the proof of Lemma 7. By the discrete Poincaré inequality, we have

where $D_{i}$ denote the discrete derivative defined as

with ${\bm{\theta}}_{-i}=(\theta_{1},\ldots,\theta_{i-1},-\theta_{i},\theta_{i+1},\ldots,\theta_{d})$. Let $\varphi_{g}({\bm{\theta}})=(\langle{\bm{\theta}},g\cdot{\bm{\theta}}\rangle/d)^{k}$, then

We have $\langle{\bm{\theta}}_{-i},g\cdot{\bm{\theta}}\rangle=\langle{\bm{\theta}},g\cdot{\bm{\theta}}\rangle-2\theta_{i}(g\cdot{\bm{\theta}})_{i}$. By Taylor expansion, the first term verifies (recall that $g\cdot{\bm{\theta}}\in{\mathscrsfs Q}^{d}$ and $\theta_{i}^{2}(g\cdot{\bm{\theta}})_{i}^{2}=1$)

where $X_{i,1}({\bm{\theta}},g)$ is on the line segment between $\langle{\bm{\theta}},g\cdot{\bm{\theta}}\rangle/d$ and $\langle{\bm{\theta}}_{-i},g\cdot{\bm{\theta}}\rangle/d$. Similarly, Taylor expansion on the second term yields

where $X_{i,2}({\bm{\theta}},g)$ is on the line segment between $\langle{\bm{\theta}}_{-i},g\cdot{\bm{\theta}}_{-i}\rangle/d$ and $\langle{\bm{\theta}},g\cdot{\bm{\theta}}_{-i}\rangle/d$.

Using Jensen’s inequality to separate each of the $4$ terms in $D_{i}\varphi_{g}({\bm{\theta}})$, using that ${\bm{\theta}}_{-i}$ and ${\bm{\theta}}$ have the same distribution, we get

Noticing that $\sup_{i,s,{\bm{\theta}},g}|X_{i,s}({\bm{\theta}},g)|\leq 1$, the second term in the above equation can be bounded by $C_{k}/d^{3}$. The first term in the above equation can be bounded using the same way as bounding the right hand side of Eq. (49) as in the proof of Lemma 7. This concludes the proof. ∎

Appendix F Kernel concentration for the cyclic group and general σ𝜎\sigma

Let the Gegenbauer decomposition of $\sigma$ be

Step 1. Finite subset $S\subseteq\{2,3,\ldots\}$. Note we have

Moreover, by the Hanson-Wright inequality as in Lemma 3, since $N$ is at most polynomial in $d$, then for any $\delta>0$, we have

Therefore, by Eq. (53), (54), (55) and (56), we have

The last equality is by Proposition 5, and the fact that

Step 4. Complete the proof. By Eq. (59), (60), (61) and (62), we have

F.2 Auxiliary lemmas

The following lemma is a reformulation of [GMMM19, Lemma 5].

where $\|{\bm{x}}\|_{2}=\|{\bm{x}}^{\prime}\|_{2}=\sqrt{d}$ such that $\langle{\bm{x}},{\bm{x}}^{\prime}\rangle/d=\gamma$ (by an invariance argument, $E_{d}$ and $E$ do not depend on the choice of ${\bm{x}}$ and ${\bm{x}}^{\prime}$). Then we have

where $\|{\bm{x}}\|_{2}=\|{\bm{x}}^{\prime}\|_{2}=\sqrt{d}$ such that $\langle{\bm{x}},{\bm{x}}^{\prime}\rangle/d=\gamma$. Note we have

where the last equality is by (b) and (c) in Lemma 9. Moreover, we have

where the last equality is by (a) and (c) in Lemma 9. Combining the two equations above proves Eq. (65).

where $\|{\bm{x}}\|_{2}=\|{\bm{x}}^{\prime}\|_{2}=\sqrt{d}$ such that $\langle{\bm{x}},{\bm{x}}^{\prime}\rangle/d=\gamma$ (by an invariance argument, $h_{d}$ and $h$ do not depend on the choice of ${\bm{x}}$ and ${\bm{x}}^{\prime}$). Then we have

For $k=0$, the result is implied by Lemma 10 by observing that $h_{d}^{\prime}=E_{d}[\sigma,\sigma]$ and $h^{\prime}=E[\sigma,\sigma]$.

For $k=1$, the result is implied by Lemma 10 by the fact that $h_{d}^{\prime}=E_{d}[u\sigma(u),\sigma^{\prime}(u)]$ and $h^{\prime}=E[u\sigma(u),\sigma^{\prime}(u)]$, and there exist constants $c_{0}>0$ and $c_{1}<1$ such that $\sigma^{\prime}(u),u\sigma(u)\leq c_{0}e^{c_{1}u^{2}/2}$. Indeed, for $\|{\bm{x}}\|_{2}=\|{\bm{x}}^{\prime}\|_{2}=\sqrt{d}$ such that $\langle{\bm{x}},{\bm{x}}^{\prime}\rangle/d=\gamma$, we have (similarly for $h^{\prime}$)