{'fraction_non_alphanumeric': 0.04989142930131562, 'fraction_numerical': 0.019670455996934476, 'mean_word_length': 4.439966648137855, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks

In this paper, we utilize a connection between compositional kernels and branching processes via Mehler's formula to study deep neural networks. This new probabilistic insight provides us a novel perspective on the mathematical role of activation functions in compositional neural networks. We study the unscaled and rescaled limits of the compositional kernels and explore the different phases of the limiting behavior, as the compositional depth increases. We investigate the memorization capacity of the compositional kernels and neural networks by characterizing the interplay among compositional depth, sample size, dimensionality, and non-linearity of the activation. Explicit formulas on the eigenvalues of the compositional kernel are provided, which quantify the complexity of the corresponding reproducing kernel Hilbert space. On the algorithmic front, we propose a new random features algorithm, which compresses the compositional layers by devising a new activation function.


Introduction
Kernel methods and deep neural networks are arguably two representative methods that achieved the state-of-the-art results in regression and classification tasks. However, unlike the kernel methods where both the statistical and computational aspects of learning have been understood reasonably well, there are still many theoretical puzzles around the generalization, computation and representation aspects of deep neural networks (Zhang et al., 2017). One hopeful direction to resolve some of the puzzles in neural networks is through the lens of kernels Recht, 2008, 2009;Cho and Saul, 2009;Belkin et al., 2018b). Such a connection can be readily observed in a two-layer infinite-width network with random weights, see the pioneering work by Neal (1996a) and Recht, 2008, 2009). For deep networks with hierarchical structures and randomly initialized weights, compositional kernels (Daniely et al., 2017b,b) are proposed to rigorously characterize such a connection, with promising empirical performances (Cho and Saul, 2009).
In this paper, we continue to study deep neural networks and their dual compositional kernels, furthering the aforementioned mathematical connection, based on the foundational work of Recht, 2008, 2009) and (Daniely et al., 2017b,a). We focus on a standard multilayer perceptron architecture with Gaussian weights and study the role of the activation function and its effect on composition, data memorization, spectral properties, algorithms, among others. Our main results are based on a simple yet elegant connection between compositional kernels and branching processes via Mehler's formula. This new connection, in turn, opens up the possibility of studying the mathematical role of activation functions in compositional deep neural networks, utilizing the probabilistic tools in branching processes. Specifically, the new probabilistic insight allows us to answer the following questions: Limits and phase transitions. Given an activation function, one can define the corresponding compositional kernel (Daniely et al., 2017b,a). How to classify the activation functions according to the limits of their dual compositional kernels, as the compositional depth increases? What properties of the activation functions govern the different phases of such limits? How do we properly rescale the compositional kernel such that there is a limit unique to the activation function? The above questions will be explored in Section 3. Memorization capacity of compositions: tradeoffs. Deep neural networks and kernel machines can have a good out-of-sample performance even in the interpolation regime (Zhang et al., 2017;Belkin et al., 2018b), with perfect memorization of the training dataset. What is the memorization capacity of the compositional kernels? What are the tradeoffs among compositional depth, number of samples in the dataset, input dimensionality, and properties of the activation functions? Section 4 studies such interplay explicitly. Spectral properties of compositional kernels. Spectral properties of the kernel (and the corresponding integral operator) affect the statistical rate of convergence, for kernel regressions (Caponnetto and Vito, 2006). What is the spectral decomposition of the compositional kernels? How do the eigenvalues of the compositional kernel depend on the activation function? Section 5 is devoted to answering the above questions. New randomized algorithms. Given a compositional kernel with a finite depth associate with an activation, can we devise a new "compressed" activation and new randomized algorithms, such that the deep neural network (with random weights) with the original activation is equivalent to a shallow neural network with the "compressed" activation? Such algorithmic questions are closely related to the seminal Random Fourier Features (RFF) algorithm in Recht (2008, 2009), yet different. Section 6 investigates such algorithmic questions by considering compositional kernels and, more broadly, the inner-product kernels. Differences to the RFF are also discussed in detail therein.
Borrowing the insight from branching process, we start with studying the role of activation function in the compositional kernel, memorization capacity, and spectral properties, and conclude with the converse question of designing new activations and random nonlinear features algorithm based on kernels, thus contributing to a strengthened mathematical understanding of activation functions, compositional kernel classes, and deep neural networks.

Related Work
The connections between neural networks (with random weights) and kernel methods have been formalized by researchers using different mathematical languages. Instead of aiming to provide a complete list, here we only highlight a few that directly motivate our work. Neal (1996b,a) advocated using Gaussian processes to characterize the neural networks with random weights from a Bayesian viewpoint. For two-layer neural networks, such correspondence has been strengthened mathematically by the work of Recht (2008, 2009). By Bochner's Theorem, Rahimi and Recht (2008) showed that any positive definite translation-invariant kernel could be realized by a two-layer neural network with a specific distribution on the weights, via the trigonometric activation. Such insights also motivated the well-known random features algorithm, random kitchen sinks (Rahimi and Recht, 2009). One highlight of such an algorithm is that in the first layer weights, sampling is employed to replace the optimization. Later, several works extended along the line, see, for instance, Kar and Karnick (2012) on the rotation-invariant kernels, Pennington et al. (2015) on the polynomial kernels, and Bach (2016) on kernels associated to ReLU-like activations (using spherical harmonics). Recently, Mei and Montanari (2019) investigated the precise asymptotics of the random features model using random matrix theory. For deep neural networks, compositional kernels are proposed to carry such connections further. Cho and Saul (2009) introduced the compositional kernel as the inner-product of compositional features. Daniely et al. (2017b,a) described the compositional kernel through the language of the computational skeleton, and introduced the duality between the activation function and compositional kernel.
One might argue that neural networks with static random weights may not fully explain the success of neural networks, noticing that the evolution of the weights during training is yet another critical component. On this front, Chizat and Bach (2018b); Mei et al. (2018); Sirignano and Spiliopoulos (2018); Rotskoff and Vanden-Eijnden (2018) employed the mean-field characterization to describe the distribution dynamics of the weights, for two-layer networks. Rotskoff and Vanden-Eijnden (2018); Dou and Liang (2019) studied the favorable properties of the dynamic kernel due to the evolution of the weight distribution. Nguyen and Pham (2020) carried the mean-field analysis to multi-layer networks rigorously. On a different tread (Jacot et al., 2019;Du et al., 2018;Chizat and Bach, 2018a;Woodworth et al., 2019), researchers showed that under specific scaling, training over-parametrized networks could be viewed as a kernel regression with perfect memorization of the training data, using a tangent kernel (Jacot et al., 2019) built from a linearization around its initialization. For a more recent resemblance between the kernel learning and the deep learning on the empirical side, we refer the readers to Belkin et al. (2018b).

Preliminary
Mehler's formula. We will start with reviewing some essential background on the Hermite polynomials that is of direct relevance to our paper.
Definition 2.1 (Hermite polynomials). The probabilists' Hermite polynomials He k (x) for non-negative integers k ∈ Z ≥0 follows the recursive definition with He 0 (x) = 1 and (2.1) We define the normalized Hermite polynomials as The set {h k : k ∈ Z ≥0 } forms an orthogonal basis of L 2 φ under the Gaussian measure φ ∼ N (0, 1) as Proposition 2.2 (Mehler's formula). Mehler's formula establishes the following equality on Hermite polynomials: for any ρ ∈ (−1, 1) and x, y ∈ R Branching process. Now we will describe the branching process and compositions of probability generating functions (PGF).
Definition 2.3 (Probability generating function). Given a random variable Y on non-negative integers with the following probability distribution define the associated generating function as Definition 2.4 (Galton-Watson branching process). The Galton-Watson (GW) branching process is defined as a Markov chain {Z L : L ∈ Z ≥0 }, where Z L denotes the size of the L-th generation of the initial family. Let Y be a random variable on non-negative integers describing the number of direct children, that is, it has k children with probability p k with k≥0 p k = 1. Begin with one individual Z 0 ≡ 1, and let it reproduce according to the distribution of Y , and then each of these children then reproduce independently with the same distribution as Y . The generation sizes {Z L : L ∈ Z ≥0 } are then defined by where Y (L) i denotes the number of children for the i-th individual in generation L.
Definition 2.6 (Activation function). Throughout the paper, we will only consider the activation functions σ (·) ∈ L 2 φ : R → R that are L 2 -integrable under the Gaussian measure φ. The Hermite expansion of σ (·) is denoted as (2.8) We will explicitly mention the following two assumptions when they are assumed. Otherwise, we will work with the activation σ (·) in Definition 2.6.
Definition 2.7 (Fully-connected MLPs with random weights). Given an activation function σ (·), the number of layers L, and the input vector x (0) := x ∈ R d 0 , we define a multi-layer feed-forward neural network which inductively computes the output for each intermediate layer (2.13) Here I d denotes the identity matrix of size d , and ⊗ denotes the Kronecker product between two matrices. The activation σ (·) is applied to each component of the vector input, and the weight matrix W ( ) in the -th layer is sampled from a multivariate Gaussian distribution MN (·, ·). For a vector v and a scalar s, the notation v/s denotes the component-wise division of v by scalar s. We remark that the scaling in (2.12) matches the standard weight initialization scheme in practice, since in the current setting x √ d l and (2.13) is effectively saying that each row W 3 Compositional Kernel and Branching Process

Warm up: Duality
We start by describing a simple duality between the activation function in multi-layer perceptrons (that satisfies Assumption 1) and the probability generating function in branching processes.
This simple yet essential duality allows us to study deep neural networks, and compare different activation functions borrowing tools from branching processes. This duality can be readily established via the Mehler's formula (Proposition 2.2). To the best of our knowledge, this probabilistic interpretation (Lemma 3.3) is new to the literature.
Lemma 3.1 (Duality: activation and generating functions). Let σ (·) ∈ L 2 φ (1) be an activation function under Assumption 1, with the corresponding Hermite coefficients {a k : k ∈ Z ≥0 } satisfying k≥0 a 2 k = 1. Define the corresponding random variable Y σ with We denote the PGF of Y σ (from Definition 2.3) as G σ (·) : [−1, 1] → [−1, 1] to be the dual generating function of the activation σ (·). Then, for any x, z ∈ R d , with ρ := x/ x , z/ z ∈ [−1, 1], we have Based on the above Lemma 3.1, it is easy to define the compositional kernel associated with a fully-connected MLP, with activation σ (·). The compositional kernel approach of studying deep neural networks has been proposed in Daniely et al. (2017b,a). To see why, let us recall the MLP with random weights defined in Definition 2.7. Then, for any fixed data input x, z ∈ R d 0 , the following holds almost surely for random weights W ( ) Motivated by the above equation, one can introduce the asymptotic compositional kernel defined by a deep neural network with activation σ (·), in the following way.
Definition 3.2 (Compositional kernel). Let σ (·) ∈ L 2 φ (1) be an activation function that satisfies Assumption 1. Define the L-layer compositional kernel K (L) σ (·, ·) : X × X → R to be the (infinite-width) compositional kernel associated with the fully-connected MLPs (from Definition 2.7), such that for any x, z ∈ X , we have Since the kernel only depends on the inner-product ρ = x/ x , z/ z , when there is no confusion, we denote for any ρ ∈ [−1, 1] (3.5) We will now point out the following connection between the compositional kernel for deep neural network and the Galton-Watson branching process. Later, we will study the (rescaled) limits, phase transitions, memorization capacity, and spectral decomposition of such compositional kernels.
Lemma 3.3 (Duality: MLP and Branching Process). Let σ (·) ∈ L 2 φ (1) be an activation function that satisfies Assumption 1, and G σ (·) be the dual generating function as in Lemma 3.1. Let {Z σ ,L : L ∈ Z ≥0 } be the Galton-Watson branching process with offspring distribution Y σ . Then for any L ∈ Z ≥0 , the compositional kernel has the following interpretation using the Galton-Watson branching process (3.6) The above duality can be extended to study other network architectures. For instance, in the residual network, the duality can be defined as follows: for x, z ∈ S d−1 , r ∈ [0, 1], and a centered activation function σ (·) (Assumption 2), define the dual residual PGF G res σ as Later in the next section, we can see the cost and benefits of adding a linear component to the PGF in the compositional behavior of it.

Limits and phase transitions
In this section, we will study the properties of the compositional kernel, in the lens of branching process, utilizing the duality established in the previous section. One important result in branching process is the Kesten-Stigum Theorem (Kesten and Stigum, 1966), which can be employed to assert the rescaled limit and phase transition of the compositional kernel.
Theorem 3.4 (Rescaled non-trivial limits and phase transitions: compositional kernels). Let σ (·) ∈ L 2 φ (1) be an activation function that satisfies Assumption 1, with {a k : k ∈ Z ≥0 } be the corresponding Hermite coefficients that satisfy k≥0 a 2 k = 1. Define two quantities that depend on σ (·), Recall the MLP compositional kernel K (L) σ (·) : R → R with activation σ (·) in Definition 3.2, and the dual PGF G σ (·) in Lemma 3.1. For any t ≥ 0, the following results hold, depending on the value of µ and µ : (ii) µ > 1 and µ < ∞. Then, there exists 0 ≤ ξ < 1 with G σ (ξ) = ξ and a unique positive random variable W σ (that depends on σ ) with a continuous density on R + . And, the non-trivial rescaled limit is Then, for any positive number m > 0, we have (3.10) The above shows that when looking at the compositional kernel at the rescaled location e −t/µ L for a fixed t > 0, the limit can be characterized by the moment generating function associated with a negative random variable M −W σ (t) = E[e −tW σ ] individual to the activation function σ . The intuition behind such a rescaled location is that the limiting kernels witness an abrupt change of value at K (L) σ (ρ) near ρ = 1 for large L (see the below Corollary 3.5). In the case µ > 1, the proper rescaling in Theorem 3.4 stretches out the curve and zooms in the narrow window of width O(1/µ L ) local to ρ = 1 to inspect the detailed behavior of the compositional kernel K (L) σ (ρ). Conceptually, the above Theorem classifies the rescaled behavior of the compositional kernel into three phases according to µ and µ , functionals of the activation σ (·). One can also see that the unscaled limit for the compositional kernel has the following simple behavior.
Corollary 3.5 (Unscaled limits and phase transitions). Under the same setting as in Theorem 3.4, the following results hold: Under additional assumptions of G σ (·) on (−1, 0) such as no fixed points or non-negativity, we can extend the above results to [−1, 1] Under the additional Assumption 2 on σ (·), for non-linear activation σ (·), we have µ > 1 and ξ = 0. Therefore, the unscaled limit for non-linear compositional kernel is (3.14) We remarks that the fact (ii) in the above corollary is not new and has been observed by Daniely et al. (2017b). They use the fact (ii) to shed light on why more than five consecutive fully connected layers are rare in practical architectures.

Memorization Capacity of Compositions: Tradeoffs
One advantage of deep neural networks (DNN) is their exceptional data memorization capacity. Empirically, researchers observed that DNNs with large depth and width could memorize large datasets (Zhang et al., 2017), while maintaining good generalization properties. Pioneered by Belkin, a list of recent work contributes to a better understanding of the interpolation regime (Belkin et al., 2018a(Belkin et al., , 2019(Belkin et al., , 2018cLiang and Rakhlin, 2018;Hastie et al., 2019;Bartlett et al., 2019;Liang et al., 2020;Feldman, 2019;Nakkiran et al., 2020). With the insights gained via branching process, we will investigate the memorization capacity of the compositional kernels corresponding to MLPs, and study the interplay among the sample size, dimensionality, properties of the activation, and the composition depth in a non-asymptotic way.
In this section, we denote X = {x i ∈ S d−1 : i ∈ [n]} as the dataset with each data point lying on the unit sphere. Specifically, we consider the following scaling regimes on the sample size n relative to the dimensionality d: 1. Small correlation: We consider the scaling regime log n d → 0, where the dataset X is generated from a probabilistic model with uniform distribution on the sphere. We name it "small correlation" since in such a case we have that sup i j |ρ ij | is vanishing small, where ρ ij = x i , x j .
2. Large correlation: We consider the scaling regime log n d → ∞, where the dataset X forms a certain packing set of the sphere. We call it "large correlation" as sup i j |ρ ij | can be close to 1.
For the results in this section, we make the Assumptions 1 and 2 on the activation function σ (·), which are guaranteed by a simple rescaling and centering of any L 2 activation function. Let K (L) ∈ R n×n be the empirical kernel matrix for the compositional kernel at depth L, with (4.1) For kernel ridge regression, the spectral properties of the empirical kernel matrix affect the memorization capacity: when K (L) has full rank, the regression function without explicit regularization can interpolate the training dataset. Specifically, the following spectral characterization on the empirical kernel matrix determines the rate of convergence in terms of optimization to the min-norm interpolated solution, thus further determines memorization.
Definition 4.1 (κ-memorization). We call that a symmetric kernel matrix , of K are well behaved in the following sense

Small correlation regime
To study the small correlation regime, we consider a typical instance of the dataset that are generated i.i.d. from a uniform distribution on the sphere.
Theorem 4.2 (Memorization capacity, small correlation regime). Consider a dataset with random And, consider the regime log n d(n) → 0. For any 0 < κ < 1 and sufficiently large n, with the compositional depth the empirical kernel matrix is well conditioned in the sense that it κ-memorizes the dataset X with probability at least 1 − exp(−c 2 n), where c 1 and c 2 are constants that do not depend on n and d.
In the small correlation regime, the above Theorem 4.2 states that in order for us to memorize a size n-dataset X , the depth L for the compositional kernel K (L) σ scales with three quantities: the linear component in the activation function a −2 1 , a factor log(nκ −1 ), and the logarithm of the regime scaling log( log n d ). Two remarks are in order. First, as the quantity log n d becomes larger, we need a larger depth for the compositional kernel to achieve the same memorization. However, such an effect is mild since the regime scaling enters logarithmically in a form log( log n d ). In other words, for i.i.d. data on the unit sphere with log n d → 0, it is indeed easy for a shallow compositional kernel (with depth at most log n) to memorize the data. Second, a −2 1 = 1 + ( k≥2 a 2 k )/a 2 1 can be interpreted as the amount of non-linearity in the activation function. Therefore, when the nonlinear component is larger, we will need fewer compositions for memorization. A simple contrast should be mentioned for comparison: memorization is only possible for linear models when d ≥ n, whereas with composition and non-linearity, d log n is enough for memorization.

Large correlation regime
To study the large correlation regime, we consider a natural instance of the dataset that falls under such a setting. The construction is based on the sphere packing.
the empirical kernel matrix is well conditioned in the sense that it κ-memorizes the dataset X , where c 3 is a constant that does not depend on n and d.
In the large correlation regime, to memorize a dataset, the behavior of the compositional depth is rather different from the small correlation regime. The depth L in Theorem 4.4 scales with three quantities: the non-linearity measured in µ − 1, a factor log(nκ −1 ) same as before, and the exponential of the regime scaling exp(2 one needs a very deep compositional kernel to achieve memorization. Second, unlike in the small correlation regime, the role of non-linearity enters in a different form here: the larger the non-linear component is, the larger the µ − 1 = k≥2 a 2 k (k − 1) is, which mitigates the compositional depth. To sum up, with non-linearity and composition, even in the d log n regime with a hard data instance, memorization is possible but with a very deep neural network.

Spectral Decomposition of Compositional Kernels
In this section, we investigate the spectral decomposition of the compositional kernel function. We study the case where the base measure is a uniform distribution on the unit sphere, denote by τ d−1 . Let S d−1 be the surface area of S d−1 . To state the results, we will need some background on the spherical harmonics. We consider the dimension d ≥ 2, and will use k ∈ Z ≥0 to denote an integer.
Definition 5.1 (Spherical harmonics, Chapter 2.8.4 in Atkinson and Han (2012) (5.1)  (2012)). Define the Legendre polynomial of degree k with dimension d to be

Then, the sets form an orthogonal basis for the space L
The following orthogonality holds (5.5) Recall that the compositional kernel K (L) σ (·) and the random variable Z σ ,L , which denotes the size of the L-th generation, as in Lemma 3.3. Then, we have the following theorem describing the spectral decomposition of the compositional kernel function and the associated integral operator.
Theorem 5.3 (Spectral decomposition of compositional kernel). Consider any x, z ∈ S d−1 . Then, the following spectral decomposition holds for the compositional kernel K (L) σ with any fixed depth L ∈ Z ≥0 : where the eigenfunctions Y k,j (·) form an orthogonal basis of L 2 τ d−1 , and the eigenvalues λ k satisfy the following formula . (5.7) The associated integral operator T (5.9) The above spectral decompositions are important because it helps us study the generalization error (in the fixed dimensional setting) of regression methods with the compositional kernel K (L) σ . More specifically, understanding the eigenvalues of the compositional kernels means that we can employ the classical theory on reproducing kernel Hilbert spaces regression (Caponnetto and Vito, 2006) to quantify generalization error. In the case when dimensionality grows with the sample size, several attempts have been made to understand the generalization properties of the inner-product kernels (Liang and Rakhlin, 2018;Liang et al., 2020) in the interpolation regime, which includes these compositional kernels as special cases.

Kernels to Activations: New Random Features Algorithms
Given any L 2 φ activation function σ (·) (as in Definition 2.6), we can define a sequence of positive definite (PD) compositional kernels K (L) σ , with L ≥ 0, whose spectral properties have been studied in the previous section, utilizing the duality established in Section 3.1. Such compositional kernels are non-linear functions on the inner-product x, z (rotation-invariant), and we will call them the innerproduct kernels (Kar and Karnick, 2012). In this section, we will investigate the converse question: given an arbitrary PD inner-product kernel, can we identify an activation function associated with it? We will provide a positive answer in this section. Direct algorithmic implications are new random features algorithms that are distinct from the well-known random Fourier features and random kitchen sinks algorithms studied in Recht (2008, 2009).
Define an inner-product kernel K(·, ·) : To define the activations given an arbitrary PD inner-product kernel, we require the following theorem due to Schoenberg (1942).
Proposition 6.1 (Theorem 1 in Schoenberg (1942)). For a fixed d ≥ 2, the inner-product kernel K(·, ·) in (6.1) is positive definite on S d−1 × S d−1 if and only if α k ≥ 0 for all k ∈ Z ≥0 in Equation (6.2). Now, we are ready to state the activation function σ f defined based on the inner-product kernel function f . One can define the following dual activation function σ f : Then, the following statements hold:

4)
where ξ is sampled from a uniform distribution on the sphere S d−1 .
The above theorem naturally induces a new random features algorithm for kernel ridge regression, described below. Note that the kernel K can be any compositional kernel, which is positive definite and of an inner-product form.
Algorithm 1: New random features algorithm for positive definite inner-product kernels K(x, z) = f ( x, z ) based on Theorem 6.2.
Result: Given a normalized dataset X = {x i ∈ S d−1 , i ∈ [n]}, an integer m, and a positive definite inner-product kernel K(x, z) = f ( x, z ), return a randomized non-linear feature matrix Φ ∈ R n×m for kernel ridge regression.

It is clear from Theorem 5.3 that all compositional kernels K (L)
σ are positive definite, though the converse statement is not true. A notable example is the kernel P k,d ( x, z ) : S d−1 × S d−1 → R, which is PD kernel but with negative Taylor coefficients, thus cannot be a compositional kernel. For the special case of compositional kernels with depth L and activation σ (·), it turns out one can define a new "compressed" activation σ L (·) ∈ L 2 φ to represent the depth-L compositional kernel. We propose the following algorithm: Algorithm 2: New random features algorithm for compositional kernels K (L) σ . Result: Given a normalized dataset X = {x i ∈ S d−1 , i ∈ [n]}, an integer m, and a compositional kernel K σ ( x, z ), return a randomized non-linear feature matrix Ψ ∈ R n×m for kernel ridge regression.
Step 1: Calculate the Taylor coefficients of K (L) Step 2: Obtain the "compressed" activation function σ L (t) = ∞ k=0 √ α k h k (t), t ∈ R; Step 3: Sample m-i.i.d. isotropic Gaussian vectors θ θ θ j ∼ N (0, I d ), and then define the non-linear feature matrix (6.6) The feature matrix satisfies lim a.s.. Let us discuss the relationship between our random features algorithms above and that in Recht (2008, 2009). Rahimi and Recht (2008) employed the duality between the PD shift-invariant kernel k(x − z) and a positive measure that corresponds to the inverse Fourier transform of k: the random features are constructed based on the specific positive measure where sampling could be a non-trivial task. In contrast, we utilize the duality between the PD innerproduct kernel and an activation function, where the random features are always generated based on the uniform distribution on the sphere (or the isotropic Gaussian), but with different activations σ (·). It is clear that sampling uniformly from the sphere can be easily done by sampling θ θ θ ∼ N (0, I d ), and returning θ θ θ/ θ θ θ .

Numerical Investigation
In this section, we will explore numerically the theory established in the previous sections. We will experiment with four common activations used in practice as a proof of concept, namely ReLU, GeLU, Swish, and Sigmoid, and four PGFs associated with non-negative discrete probability distributions including Poisson(λ), Binomial(n,p), Geometric(p), and Uniform(0, n). To execute the theory numerically, we introduce a simple and general Algorithm 3 for estimating the Hermite coefficients of any activation function σ (·), with provable guarantees. The numerical stability of this algorithm to estimate the Hermite coefficients can be seen in Figure 7. The truncation level considered is T = 20. We will use this level throughout the rest of the experiments in this section.

Duality: Activations and PGFs
According to Lemma 3.1, there is a duality between activation functions σ (·) (normalized as in 1) and PGFs G σ (·) (of a discrete non-negative probability distribution). In the first two plots in Figure  2, we start from a probability distribution, and construct its corresponding activation function.

Algorithm 3: Algorithm for estimating the Hermite coefficients of an activation σ (·).
Result: Given an activation function σ (t) = ∞ k=0 a k h k (t) ∈ L 2 φ and a truncation level T , return an estimate of the Hermite coefficients {a k } T k=0 .

Kernel limits
In this section, we will illustrate the compositional behavior of the kernels, both in the unscaled (Corollary 3.5) and rescaled (Theorem 3.4) cases. We start with Figure 3 on the compositional behavior of unscaled kernels K (L) σ (ρ) as a function of ρ ∈ [−1, 1], without centering the activation functions. According to Corollary 3.5, we know that the unscaled limits of compositional kernels are determined strictly by a phase transition of µ at 1. On the interval (−1, 1), ReLU and Sigmoid's composite kernels converge to 1, while GeLU and Swish's converge to their corresponding extinction probability. In Figure 4 we plot the compositional behavior of the K (L) σ (ρ) for centered activations σ : For centered ReLU, GeLU, Swish, the limit approaches 0 for ρ ∈ [−1, 1), and approaches 1 at ρ = 1. For centered Sigmoid, a 1 ≈ 1, which explains the resemblance to the linear kernel.
On the other hand, for rescaled kernels K (L) σ (e −t/µ L ) as a function of t ∈ [0, ∞), non-trivial limits that depend on σ (·) exist, when µ < ∞. In the un-centered and rescaled case (Theorem 3.4), we have that ReLU and Sigmoid's compositional kernels converge to 1, while GeLU and Swish's ones approach a non-trivial limit, shown in Figure 5. If we center the activations, all rescaled kernels will approach non-trivial limits as seen in Figure 6.
In terms of the convergence speed of kernels to their unscaled limit, Theorem 4.2 explains how fast the curve flattens around 0, and Theorem 4.4 on the rate it flattens around 1. The convergence speed, in fact, determines the memorization capacity of composition kernels. To flatten around 0, we need the number of compositions to scale with 1 log a −2 1 , while to flatten around 1, we need the compositional depth to scale with 1 µ−1 . For example, Sigmoid has µ ≈ 1.03 and a 2 1 ≈ 0.99, thus explaining slow convergence compared to the other activations. Table 2 summarizes the crucial quantities that determine the compositional behavior for each activation.

Applications to datasets: new random features algorithm
In this section, we will investigate the "compressed" activations obtained from compositional kernels to generate random features, as in Algorithm 2. In Figure 7, we plot the shape of the compressed activations. We will test the validity of the new random features Algorithm 2 on two datasets, MNIST and CIFAR10. For each dataset, we run multi-class logistic regression (a  Table 2: Approximations of µ, µ (from Theorem 3.4), and a 1 (from Definition 2.6). For each activation, there are two columns: values for un-centered activation (left) and values for centered activation (right). simple one-layer neural network) with 10 categories, using the random features generated by Algorithm 2. For each dataset, we consider four activations and three compositional depths, in total 12 experiments. We run vanilla stochastic gradient descent as the training algorithm. The results are plotted in Figure 8 and the numerical results are displayed in Table 8. We remark that the generalization gap, that is the difference between training accuracy and test accuracy, is smaller for L = 3 than for L = 1 in the case of using the activation functions ReLU, GeLU, and Swish.   We used 40 epochs for MNIST and 100 epochs for CIFAR10. The number of random features was set to m = 1024 (yielding 10 × 1024 trainable parameters), and the learning rate was set to 0.1.

Proofs in Section 3
Proof of Lemma 3.1. By properties of the normal distribution, we have where N ρ denotes the standard bivariate normal distribution with correlation ρ = x/ x , z/ z . Expand the above expression explicitly and use Mehler's formula in Proposition 2.2 to obtain Proof of Lemma 3.3. We can prove by induction on L. For L = 0, it follows from the definition that For L ≥ 1, we have by induction We will use the following facts about branching process and composition of PGFs.
Proposition 8.1 (Composition of PGFs). The PGF associated with the size of the L-th generation Z L in a branching process satisfies Theorem 8.2 (Kesten and Stigum (1966), See also Theorem 12.3 in Lyons and Peres (2016)

(Compositional limit). lim L→∞ G
Proof. Note that G σ (·) has a fixed point at 1 and it is continuous. Therefore, ξ is well defined. The first two properties extinction and fixed points are just a restatement of Proposition 2.5. Let's prove the third property compositional limit. There are two cases ξ = 1 and ξ < 1.
Remark 8.4. Under the same notation as Proposition 8.3, we will state three sufficient conditions for which the compositional limit property of G σ extends for ρ ∈ (−1, 1): 1. (Reduction to positive side). G σ (·) is non-negative; for example, an even function G σ (·). In this case, after the first iteration we will be in the realm of [0,1], that is G σ (ρ) ∈ [0, 1], and the result follows by the compositional limit property applied to G σ (ρ).

(Extension of fixed points)
. G σ (·) has only two fixed points ξ and 1; for example, a convex function G σ (·). In this case, the result follows because the proof of compositional limit property for ρ ∈ [0, ξ] relies solely on the fixed points property. Therefore, we can extend the part in which ρ ∈ (0, ξ] to ρ ∈ (−1, ξ). The case t = 0 follows immediately from the fact that G σ (1) = 1.

(Centered Activation
then K is diagonally dominant and satisfies the κ-memorization property.
Lemma 8.6 (Contraction rate). Let X = {x i } i∈ [n] be a dataset of size n with no repetition of data points, 1≤i,j≤n will κ-memorizes X for any compositional depth L that satisfies Proof. We have the following inequality for any ρ such that ρ ∈ (0, δ] Hence, we obtain the sequence of inequalities and therefore One can easily verify that the lower bound on L suffices to ensure (8.17).

Small correlation
Consider the small correlation regime 1, when the correlation sup 1≤i<j≤n |ρ ij | = o(1) as log(n) d → 0. We consider a typical instance of the data where such small correlation is guaranteed with high probability, due to the following lemma.
with probability at least 1 − n −c 2 , were c 0 and c 2 are constants that do not depend on n and d.  (8.25) and invoke the following inequality, which is sharp around 0, we have Therefore, for sufficiently large n, we have L ≥ log n + log κ −1 − log δ −1 log(a 2 1 + (1 − a 2 1 )δ)) −1 for some constant c 1 that does not depends on n and d.

Large correlation
We will be in large correlation regime 2, when the correlation sup 1≤i<j≤n |ρ ij | = 1 − o(1) as log n d → ∞. We consider a typical instance of the data where such large correlation arises in the sphere packing/covering setup. (8.31) Proof of Lemma 8.10. The upper bound follows since Moreover, recall that every minimal r-packing is a maximal r-covering, thus, N r ≤ K r . Now, for the lower bound, let's calculate the surface area of the hyper-spherical cap of a covering ball of radius r defined in the following way for any x 0 ∈ S d−1 . By Pythagora's theorem, one can calculate the height of the cap as h = r 2 2 . The bottom of the cap is a d −2 dimensional sphere of radius f (h) := 1 − (1 − h) 2 . Therefore, the surface area of the cap Cap r (x 0 ) is By Gautschi's inequality, for d ≥ 3, we have Proof. By definition, any r-packing polarization set is a r-packing set. Therefore, the upper bounds P r ≤ K r follows. Now, consider any 2r-maximal packing set X = {x 1 , . . . , x n } of the sphere. Define the polar neighborhood of x i of radius r as Consider a simple graph G with vertices X and edges (x i , x j ) if x j ∈ PS(x i ) or x i ∈ PS(x j ). We claim that each vertex has at most one edge. Otherwise, consider a vertex x i adjacent to both x k and x . Then, we must have Thus, x − x k ≤ 2r, which contradicts the definition of a packing set. Therefore, we would need to remove at most n 2 vertices of the graph G to get a graph G ⊂ G with no edges. Therefore, the graph G has at least n 2 vertices and the vertices form an r-polarized packing set. The rest of the conclusions follow by Lemma 8.10.

Proofs in Section 5
Proof Therefore, one can apply the Funk-Hecke formula (Theorem 2.22 in Atkinson and Han (2012)) to obtain Recall that K (L) σ (t) = P(Z σ ,L = )t . Let us calculate the following expression explicitly through the Rodrigues representation formula (Theorem 2.23 and Proposition 2.26 in Atkinson and Han (2012)) for the Legendre polynomial, for ≥ k and by the Addition Theorem 2.9 in Atkinson and Han (2012) Atkinson and Han (2012), we know that for any g ∈ L 1 (d−3)/2 , x, z ∈ S d−1 and k ≥ 0