PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration

Song Mei, Theodor Misiakiewicz, Andrea Montanari

arXiv:2101.10588v1math.STstat.MLstat.TH

TL;DR

The paper asks how KRR test error depends on the sample size and target, and how many random features are needed to match KRR. It characterizes random-features ridge regression across sample-size and feature-count regimes, finding that its error tracks KRR when features outnumber samples and that further overparameterization does not improve it.

  • Problem

    The paper asks how KRR test error depends on sample size and target, and how large N must be for random-features regression to match KRR.

    Source: §1.1 · p. 5

  • Method

    The paper characterizes random-features ridge regression across sequences of sample size, feature count, and dimension.

    Source: §1.1 · p. 3, §1.2 · p. 5

  • Results

    When n ≪ N, RFRR has the KRR projection risk, and for λ = 0 its interpolator is optimal among kernel methods.

    Source: §1.2 · pp. 6–7

  • Takeaways & Limitations

    Once N is much larger than n, further overparameterization does not improve statistical behavior.

    Source: §1.2 · p. 7

    The sharp separation in the main result uses a spectral-gap assumption, whose transition may be less sharp for targets with substantial mass near the cutoff eigenfunctions.

    Source: §2.2 · p. 13

Abstract

from arXiv · show

Consider the classical supervised learning problem: we are given data $(y_i,{\boldsymbol x}_i)$, $i\le n$, with $y_i$ a response and ${\boldsymbol x}_i\in {\mathcal X}$ a covariates vector, and try to learn a model $f:{\mathcal X}\to{\mathbb R}$ to predict future responses. Random features methods map the covariates vector ${\boldsymbol x}_i$ to a point ${\boldsymbol \phi}({\boldsymbol x}_i)$ in a higher dimensional space ${\mathbb R}^N$, via a random featurization map ${\boldsymbol \phi}$. We study the use of random features methods in conjunction with ridge regression in the feature space ${\mathbb R}^N$. This can be viewed as a finite-dimensional approximation of kernel ridge regression (KRR), or as a stylized model for neural networks in the so called lazy training regime. We define a class of problems satisfying certain spectral conditions on the underlying kernels, and a hypercontractivity assumption on the associated eigenfunctions. These conditions are verified by classical high-dimensional examples. Under these conditions, we prove a sharp characterization of the error of random features ridge regression. In particular, we address two fundamental questions: $(1)$~What is the generalization error of KRR? $(2)$~How big $N$ should be for the random features approximation to achieve the same error as KRR? In this setting, we prove that KRR is well approximated by a projection onto the top $\ell$ eigenfunctions of the kernel, where $\ell$ depends on the sample size $n$. We show that the test error of random features ridge regression is dominated by its approximation error and is larger than the error of KRR as long as $N\le n^{1-\delta}$ for some $\delta>0$. We characterize this gap. For $N\ge n^{1+\delta}$, random features achieve the same error as the corresponding KRR, and further increasing $N$ does not lead to a significant change in test error.

1 Introduction

The introduction studies test-error behavior for kernel ridge regression and random-features ridge regression as sample size and feature count grow, relating estimated target-function components to the smaller quantity. It also defines the deterministic and in-probability asymptotic notation used in the paper.

1.1 Background

  • RFRR uses random features and ridge regression, while KRR uses a kernel-defined feature space; the paper focuses on these methods, though linearized neural networks provide related motivation.In the neural tangent model, features are gradients at random initialization and generally are not independent as in the random-features construction.Source: §1.1 · pp. 3–4

1.2 Summary of main results

  • The characterization is pointwise for any target function, up to errors negligible relative to null risk, under high-dimensional assumptions including hypercontractivity and kernel-diagonal concentration.A spectral-gap condition is used for RFRR but is not required for KRR; examples include the sphere and the hypercube with uniform measure.Source: §1.1 · p. 5, §1.2 · pp. 5–6
  • When n ≪ N, RFRR’s test error is E{(P>m f*(x))²} + o(1)·E{f*(x)²}; when n ≫ N, it is E{(P>M f*(x))²} + o(1)·E{f*(x)²}.The same characterization applies to KRR when N = ∞, and no kernel machine achieves smaller error.Source: §1.2 · p. 6
  • For N ≥ n^(1+δ), RFRR matches KRR’s test error, further overparametrization does not improve it, and minimum-norm interpolation is optimal among kernel methods.These results hold for λ ∈ [0, λ*]; the stated growth condition is mainly dictated by the proof technique.Source: §1.2 · p. 7

1.3 Related literature

  • Unlike [GMMM19], this work treats finite n and N with broader data, kernel, and activation assumptions, using decoupling and matrix concentration methods.[GMMM19] considered n = ∞ or N = ∞ and special distribution, kernel, and activation settings.Source: §1.3 · p. 8

1.4 Notations

  • The paper defines O_d, o_d, Ω_d, ω_d, and Θ_d relations for asymptotic comparisons, with d marking the variable of the asymptotics.Source: §1.4 · p. 8
  • For random-variable sequences, O_d,P and o_d,P denote bounds and convergence to zero in probability, with Ω_d,P, ω_d,P, and Θ_d defined correspondingly.Source: §1.4 · pp. 8–9

2 Generalization error of random features ridge regression

This section develops a spectral framework for characterizing random-features ridge-regression error, states high-probability guarantees across sample- and feature-size regimes, and applies them to sphere and hypercube covariates, including how test risk varies with sample size and feature count.

2.4 Examples: The binary hypercube and the sphere

  • The sphere and hypercube examples apply the general theorem; the sphere result closes the main problem left unsolved in [GMMM19].The examples use covariates and feature weights distributed uniformly over the same domain.Source: §2 · p. 9, §2.4 · p. 14

2.1 Random features models, kernels, and their spectral decomposition

  • The framework represents random features through a compact integral operator whose spectral decomposition yields kernel eigenfunctions and an associated reproducing kernel Hilbert space.The framework permits a general subspace of L2(Xd) for modeling applications.Source: §2.1 · pp. 9–10

2.2 Assumptions

  • The assumptions require hypercontractivity, sufficiently slow eigenvalue decay, concentration of truncated-kernel diagonals, and a spectral gap separating effective dimensions from sample and feature counts.The spectral gap makes the transition between estimated and unestimated target-function components sharp.Source: §2.2 · pp. 12–13

2.3 A general theorem

  • As N tends to infinity the random kernel converges to its expectation, recovering kernel ridge regression; as n tends to infinity, only approximation error remains.These limiting characterizations are established separately from Theorem 1.Source: §2.3 · p. 13
  • The smaller of sample size n and feature count N nearly determines test error; once N≫n, adding neurons has little effect, with N≈n^(1+δ) suggested for efficiency.The theorem treats overparameterized and underparameterized regimes under its feature-map concentration and spectral-gap assumptions.Source: §2.3 · pp. 13–14

2.4 Examples: The binary hypercube and the sphere

  • For the sphere and hypercube, Theorem 2 gives high-probability guarantees when d^S+δ₀ ≤ N ≤ d^(S+1)−δ₀, with regimes N ≥ n d^δ or n ≥ N d^δ and regularization scales O_d(1) or O_d(n/N), respectively.Both regimes allow λ = 0 identically.Source: §2.4 · p. 16
  • The test risk peaks when N ≈ n, a phenomenon characterized in the proportional regime N ≍ d, n ≍ d in [HMRT19] [MM19].Figure 1 shows the peak around the interpolation threshold.Source: Figure 1 · p. 17, §2.4 · p. 17
  • The risk plot appears symmetric under exchanging N and n, consistent with both limiting generalization ability in Theorems 1 and 2.Figure 1 describes symmetry around N ≈ n.Source: Figure 1 · p. 17, §2.4 · p. 17
  • For N, n ≍ d^3, risk remains bounded away from zero; consistent estimation in this case requires N, n ≫ d^4.Source: §2.4 · p. 17
  • For fixed n, near-optimal test error is achieved when N ≍ n^(1+δ*) for a small positive δ*.Source: §2.4 · p. 17

3 Generalization error of kernel machines

The section establishes lower bounds for general kernel methods and characterizes KRR without requiring a spectral gap. It approximates KRR through a population ridge problem with an effective regularization parameter.

3.2 Assumptions on the kernel

  • The kernel assumptions simplify to conditions on H_d rather than the activation function, and the analysis removes the spectral-gap requirement.The assumptions include hypercontractivity, eigenvalue decay, and concentration of kernel diagonal elements.Source: §3 · p. 18, §3.2 · pp. 19–20

3 Generalization error of kernel machines

  • The section considers i.i.d. covariates and responses formed from a target function plus independent Gaussian noise.The target function belongs to D_d.Source: §3 · p. 18

3.1 Background on kernel methods

  • A positive semidefinite kernel can be represented as an expectation over random features, making kernel methods an infinite-feature limit of random-feature models.The feature representation depends on a choice of kernel square root.Source: §3 · p. 17, §3.1 · p. 18

3.3 Lower bound for general kernel methods

  • No kernel method achieves non-trivial accuracy on target-function components beyond the first m(d) eigenvectors, up to the stated error term.The lower bound applies to general kernel methods and also yields a lower bound for KRR.Source: §3 · p. 18, §3.3 · p. 20

3.4 The risk of kernel ridge regression

  • KRR is approximated by population ridge regression with an effective regularization parameter, and its risk can be characterized without assuming a spectral gap.The effective regularization accounts for the trace of the kernel operator's tail spectrum.Source: §3 · p. 18, §3.4 · p. 21

A Approximation error of random features model

This appendix studies the approximation error of a finite random-features function class in the infinite-data setting. It states a separate theorem and uses it to support a lower bound for general kernel methods.

A Approximation error of random features model

  • The approximation error is treated as the generalization error of a finite-neuron random-features model with infinite data.The appendix states a separate theorem because Theorem 1 cannot be applied directly with n = ∞.Source: A Approximation error of random… · p. 25
  • The approximation-error theorem also supplies the lower bound for general kernel methods stated in Theorem 3.The appendix divides the theorem statement, proof, and technical concentration results among Sections A.1–A.4.Source: A Approximation error of random… · p. 25

A.1 Assumptions and theorem

The appendix states assumptions for the feature-kernel operators and a theorem giving lower and upper bounds on random-features approximation error under additional conditions.

A.1 Assumptions and theorem

  • Feature-kernel concentration assumptions cover finite-eigenspace hypercontractivity, eigenvalue decay, and upper and lower bounds on kernel diagonal elements.A separate spectral-gap assumption is stated at the specified neuron and eigenvalue levels.Source: §A.1 · pp. 25–26
  • Theorem 5 gives lower and upper bounds on random-features approximation error under distinct additional activation-function assumptions.The lower bound uses Assumptions 6.(d) and 7.(a); the upper bound uses Assumptions 6.(c) and 7.Source: §A.1 · p. 26
  • The lower bound in Theorem 5 yields the general-kernel-method lower bound by taking the activation function to be the kernel.The stated kernel conditions imply the assumptions needed for that application.Source: §A.1 · p. 26

A.2 Proof of Theorem 5.(a): lower bound on the approximation error

The proof of the approximation-error lower bound reduces to controlling two quantities using propositions on feature vectors and the kernel matrix.

A.2 Proof of Theorem 5.(a): lower bound on the approximation error

  • The proof reduces the lower-bound argument to controlling the operator norm of U^-1 and the squared norm of V_>M through two propositions.These quantities arise in the bound used to prove Theorem 5.(a).Source: §A.2 · p. 27
  • The proof invokes a proposition on the expected norm of V and a separate lower-bound proposition for the kernel matrix U.The kernel-matrix proposition is stated under feature-kernel concentration and spectral-gap assumptions.Source: §A.2 · pp. 27–28
  • Combining the kernel-matrix bound with the preceding estimate completes the proof of Theorem 5.(a).The lower bound for general kernel methods follows from Theorem 5.(a).Source: §A.2 · p. 28

A.3 Proof of Theorem 5.(b): upper bound on the approximation error

The proof represents the empirical kernel matrix as a rank-M component plus a normalized tail component, then uses a matrix-inverse identity in its argument about S.

A.3 Proof of Theorem 5.(b): upper bound on the approximation error

  • U is decomposed into the rank-M term ΦD²Φᵀ and the tail term κ₍>M₎(Λ + ∆).Here κ₍>M₎ is the trace of the tail kernel operator, and Λ normalizes its diagonal entries.Source: §A.3 · p. 29
  • The proof applies the Sherman-Morrison-Woodbury formula to express I_M − S as (I_M + Lᵀ(Λ + ∆)⁻¹L/κ₍>M₎)⁻¹.This is the displayed identity used in the proof of the concentration lemma for S.Source: §A.3 · p. 29

A.4 Structure of the empirical kernel matrix

The section characterizes the empirical kernel matrix through a rank-M spike and a tail component, with its structure supported by top-eigenvector concentration and off-diagonal bounds.

A.4.2 Bounding the off-diagonal part of the matrix U>M

  • The off-diagonal tail matrix has vanishing operator norm: its expected norm is O_d(N^(−δ′))κ₍>M₎ for some δ′ > 0.The proof invokes Proposition 4 under Assumptions 6.(a), 6.(b), and 7.(a).Source: §A.4 · pp. 30–31

A.4 Structure of the empirical kernel matrix

  • Under additional Assumptions 6.(c), 6.(d), and 7.(b), empirical kernel matrix U is a sum of a rank-M spike with eigenvalues ≫ Tr(Ud,>M) and a full-rank matrix with eigenvalues of order Tr(Ud,>M).Source: §A.4 · p. 31
  • The spike has an approximate diagonalization whose feature matrix is approximately orthogonal, with ˜D² ⪰ N(d)^δ₀Tr(Ud,>M)·I_N.The lower bound is stated under Assumption 7.(b).Source: §A.4 · p. 31

A.4.1 Concentration of the top eigenvectors

  • For diverging D and N, Proposition 3 extends the fixed-D orthonormality result to a concentration bound with δ = K(q)D log(D∨N)/N^(1−1/q).The proposition assumes moment bounds for the sampled orthonormal functions.Source: §A.4.1 · pp. 31–32

A.5 Proof of Proposition 4

The proof of Proposition 4 decomposes the operator and bounds the off-diagonal matrix through decoupling and estimates on its blocks.

A.5 Proof of Proposition 4

  • Proposition 5 supplies a vanishing off-diagonal bound for a kernel matrix under its stated operator and function assumptions.Proposition 4 applies this result after decomposing the operator into low- and high-index parts.Source: §A.5 · pp. 33–34
  • The proof uses matrix decoupling and conditional block estimates to control the expected operator norm of ∆.For a subset T, the displayed bound uses Σ(T) and Γ(T) to control E_T[∥∆_(T,Tᶜ)∥op].Source: §A.5 · p. 34
  • Hypercontractivity supplies estimates for both Σ(T) and Γ(T), which are combined to bound E[∥∆∥op].The proof combines the estimates in its final step to obtain a bound on the expected operator norm.Source: §A.5 · pp. 34–35

A.5.1 Auxiliary lemmas

The auxiliary lemmas provide concentration and moment tools used in the proofs; the following section organizes the proof of the random-features generalization theorem.

A.5.1 Auxiliary lemmas

  • A random partition of matrix indices supports the decoupling argument used to control off-diagonal blocks.The proof selects each index independently with probability 1/2.Source: §A.5.1 · p. 35
  • For the kernel formed from hypercontractive orthonormal functions, its 2q-moment is bounded by C(q)² times its second-moment norm.The displayed inequality is derived using hypercontractivity and orthonormality.Source: §A.5.1 · p. 36
  • Under the stated assumptions, the maximum sampled tail diagonal and maximum sampled squared-kernel row expectation are each O_P(N(d)^δ) times their corresponding population expectations.The two bounds are given for the tail kernel and for the full kernel.Source: §A.5.1 · p. 37

B Generalization error of random features model: Proof of Theorem 1

  • Theorem 1’s overparametrized proof is presented separately; the underparametrized proof is omitted in favor of comments on where it differs.The appendix also defers feature-matrix structure and concentration results to later subsections.Source: B Generalization error of random… · p. 38

B.1 Proof of Theorem 1 in the overparametrized regime

The overparameterized proof controls the random-features test risk by decomposing it into terms and bounding them using the feature matrix’s singular-value structure. The same proof extends to the underparameterized case through a parameter mapping.

Underparameterized case

  • The underparameterized proof follows by exchanging n with N, m with M, and replacing λ by Nλ/n for the symmetric bounds.The text notes that some bounds require corresponding replacements.Source: §B.1 · pp. 38, 41

Risk decomposition

  • The proof decomposes the risk and controls its terms using bounds on the feature matrix and related quantities.These bounds are stated in Proposition 7 and serve as the main tools for the remainder of the proof.Source: §B.1 · pp. 39–40

Proposition 6: Structure of the feature matrix Z

  • The feature matrix has m large singular-value spikes associated with its low-degree component, while the remaining singular values are approximately κ>m^1/2.The spike singular vectors are approximately spanned by those of the low-degree component.Source: §B.1 · p. 40

Proposition 7: Bounds

  • Proposition 7 provides bounds on U>m, f, and V>m under the overparameterized-regime assumptions.The stated bound on U>m is n/N · ||U>m||op = κ>m · od,P(1).Source: §B.1 · pp. 40–41

B.2 Proof of Proposition 6: Structure of the feature matrix Z

This section analyzes the feature matrix by separating its low- and high-degree components, establishing its singular-value structure and alignment with low-degree feature spaces. It also develops bounds in the underparametrized regime and concentration results in the overparametrized regime, controlling the high-degree matrix’s normalized Gram matrix and its cross term with low-degree features.

B.2 Proof of Proposition 6: Structure of the feature matrix Z

  • The normalized feature matrix has m large singular values associated with the low-degree component and n − m small singular values associated with the high-degree component.The corresponding left and right singular vectors are approximately spanned by the normalized low-degree feature maps.Source: §B.2 · p. 44

B.2.1 Auxiliary lemmas

  • The auxiliary null-space lemma shows that projecting the noise matrix onto the top left singular vectors leaves a component approximately orthogonal to the right singular vectors.The lemma assumes N ≥ n + m, n ≥ m, and a noise-matrix Gram matrix close to the identity in operator norm.Source: §B.2.1 · p. 46

B.3 Proof of Proposition 7: technical bounds in the overparametrized regime

  • The proof of Proposition 7 establishes its claims in a different order than they are stated.Source: §B.3 · p. 48

B.3.1 Proof of claim (c)

  • The proof of Proposition 7(c) invokes hypercontractivity and Markov's inequality with m ≤ n^(1−δ0) for fixed δ0 > 0.The supplied passage does not include the bound obtained.Source: §B.3.1 · p. 48

B.3.2 Proof of Proposition 7.(a)

  • Proposition 7(a)'s proof bounds a normalized ridge-resolvent feature operator by O_d,P(1).The argument splits the feature matrix into large- and small-singular-value components and combines the resulting bounds.Source: §B.3.2 · p. 51

B.3.3 Proof of Proposition 7.(b)

  • For Proposition 7(b), the proof applies Theorem 6 to U>m under the stated assumptions and N ≥ n^(1+δ0).The displayed passage defines κ>M = Tr(Hd,>M), but does not include the resulting bound.Source: §B.3.3 · p. 51

B.3.5 Bounds in the underparametrized regime

  • In the underparametrized regime, the proof bounds the error using a decomposition into low- and high-degree components and singular-value estimates for the feature matrices.It combines the component bounds with estimates for the smallest singular values to obtain the stated bound.Source: §B.3.5 · pp. 52, 54

B.4 Concentration of the random features kernel matrix ZTZ

  • Proposition 8 addresses the overparametrized case N(d) ≥ n(d)^(1+δ0), for fixed δ0 > 0, under feature-map concentration (Assumption 1) and spectral-gap (Assumption 2) conditions at the stated parameter levels.Source: §B.4 · p. 55
  • Under the same overparametrized conditions, the normalized cross term between high-degree features and low-degree eigenfunctions is bounded by a vanishing operator-norm error.The proof uses the zero cross second moment and an asymmetric random-matrix concentration bound.Source: §B.4 · p. 56

C Generalization error of kernel ridge regression: Proof of Theorem 4

This section proves Theorem 4 and points to a second version under different assumptions. The alternative relaxes Assumption 4.(c) and instead requires a gap condition on the kernel eigenvalues.

Proof of Theorem 4

  • This section proves Theorem 4 and then proves a different version in Section C.2 under somewhat different assumptions, relaxing Assumption 4.(c) and imposing a gap condition on the kernel eigenvalues.Source: C Generalization error of kernel ridge… · p. 57

Alternative theorem version

Assumption change

C.1 Proof of Theorem 4

The proof expresses KRR test error through the empirical kernel matrix, decomposes the risk, and uses auxiliary matrix bounds. A second theorem version weakens the diagonal-concentration requirement while adding a spectral-gap condition.

C.1 Proof of Theorem 4

  • The proof expresses KRR test error using the empirical kernel matrix and decomposes the risk after writing y = f + ε.The KRR estimator and resulting test error are introduced in this proof section.Source: §C.1 · p. 57, Step 2. Decompose the risk · p. 58

Step 2. Decompose the risk

  • The bound equates the operator norm of M^(1/2)(H + λI_n)^(-2)M^(1/2) with that of (H + λI_n)^(-1)M(H + λI_n)^(-1), and gives o_{d,P}(1).Source: Step 2. Decompose the risk · p. 62

C.1.1 Auxiliary lemmas

  • The auxiliary lemmas show that the matrix R approximates the shrinkage matrix S≤m, with ||R − S||op = od,P(1).They also establish that ΨTΨ/n approaches the identity in operator norm.Source: §C.1.1 · pp. 64–65

C.2 Kernel ridge regression under relaxed assumptions on the diagonal

  • Theorem 8 gives a KRR result under relaxed diagonal assumptions, replacing the earlier concentration condition with a sub-polynomial upper bound and adding an eigenvalue gap condition.The modified assumptions also specify a lower bound on diagonal terms and permitted regularization regimes.Source: §C.2 · p. 65

C.2.1 Proof outline for Theorem 8

The proof outline derives kernel-matrix bounds from spectral decompositions and assumptions, then applies perturbation estimates to control terms in the auxiliary lemmas.

C.2.1 Proof outline for Theorem 8

  • The cited passage states this lower-bound chain for the matrix expression: H + λIn ⪰ κH(ΛH + ∆H) + λIn ⪰ Ωd,P(n−δ) · κH · In.Source: §C.2.1 · p. 66
  • The proof handles T1 through T5 by adapting Section C.1’s computations, replacing order-one bounds with n-dependent rates.The replacements are o_d,P(1) → O_d,P(n^-δ0) and O_d,P(1) → O_d,P(n^δ), for arbitrarily small δ > 0.Source: §C.2.1 · p. 66
  • Equations (179), (180), and (181) are used to bound T21, T23, and T3–T5, respectively.These bounds are part of the updated auxiliary lemmas from Section C.1.1.Source: §C.2.1 · p. 67
  • The proof decomposes G into T1 and T2, bounds T1, and simplifies T2 using the Sherman-Morrison-Woodbury formula.The subsequent argument uses the resulting bounds to establish the stated auxiliary estimates.Source: §C.2.1 · pp. 67–68

D Proof of Theorem 2: generalization error of RFRR on the sphere and hypercube

This appendix establishes the assumptions and harmonic-analysis foundations used in the proof of Theorem 2 for random-features ridge regression on the sphere and hypercube, including polynomial convergence and hypercontractivity results.

D.1 On the sphere

  • On the sphere, the proof orders activation eigenvalues by spherical-harmonic degree, chooses cutoffs m and M at degrees s and S, and checks Theorem 1’s assumptions.It also uses hypercontractivity for low-degree polynomials and the constancy of the truncated-kernel diagonal.Source: §D.1 · pp. 70–71

D.2 On the hypercube

  • The hypercube proof follows the sphere argument, but its eigenvalue degeneracy motivates the additional Assumption 3(c), which is checked for a class of smooth activations.The stated sufficient condition bounds a fixed derivative of the activation by c0 exp(c1 x^2/4), with c1 < 1.Source: §D.2 · p. 73

E.1.1 Functional spaces over the sphere

  • On the sphere, homogeneous harmonic polynomials restricted to the sphere form degree-indexed spaces whose orthogonal decomposition provides the functional-space basis for the proof.The appendix defines these spaces and gives their dimensions.Source: §E.1.1 · p. 74

E.1.2 Gegenbauer polynomials

  • For rotationally invariant kernels, degree-k spaces are eigenspaces, and Gegenbauer polynomials represent the corresponding spherical-harmonic projectors.The kernel eigenvalue is indexed by harmonic degree.Source: §E.1.2 · p. 75

E.1.3 Hermite polynomials

  • As dimension grows, fixed-degree Gegenbauer polynomials converge to Hermite polynomials under the corresponding measure limit.The appendix uses weak convergence of the rescaled spherical-coordinate measure to the standard Gaussian.Source: §E.1.3 · p. 76

E.2.1 Fourier basis

  • The hypercube appendix introduces its uniform-measure function space and decomposes it into degree-indexed polynomial spaces.Its Fourier basis consists of degree-ℓ functions indexed by subsets of coordinates of size ℓ.Source: §E.2 · p. 76, §E.2.1 · pp. 76–77

E.2.2 Hypercubic Gegenbauer

  • Hypercubic Gegenbauer polynomials form an orthogonal basis for the distribution of the coordinate sum under the uniform hypercube measure.Their inner products across distinct degrees vanish.Source: §E.2.2 · p. 77
  • For each fixed k, the rescaled hypercubic Gegenbauer polynomials converge to the Hermite polynomials.Source: §E.2.2 · p. 77

E.3 Hypercontractivity of Gaussian measure and uniform distributions on the sphere and the hypercube

  • Hypercontractivity lemmas cover degree-ℓ polynomials on the hypercube, sphere, and Gaussian measure for q ≥ 2.Source: §E.3 · p. 78
  • Gaussian hypercontractivity is a direct consequence of hypercube hypercontractivity.Source: §E.3 · p. 78

Related papers

Loading 2101.10588v1…