A Class of Random-Kernel Network Models
James Tian · 2025
Read A Class of Random-Kernel Network Models by James Tian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01090.txt.
Introduction
James Tian introduces a class of network models that blend random features with layered kernels, functions that measure how alike two inputs are. In these models, depth comes from stacking fixed kernel steps, while chance enters only in the last layer. The design extends older random feature models, which use one random layer to approximate complex functions.
Tian proves that the deeper form can match some functions using fewer random samples than any shallow form could. That gap is stated as a depth separation result about sample cost. The finding matters because it shows layering itself, not just more data or more units, can make learning more efficient. It gives theory support for building such models with depth in mind.
Catalog record
| CREATOR | James Tian |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-01090
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Class of Random-Kernel Network Models James Tian Abstract . We introduce random-kernel networks, a multilayer extension of random feature models where depth is created by deterministic kernel composition and randomness enters only in the outermost layer. We prove that deeper constructions can approximate certain functions with fewer Monte Carlo samples than any shallow counterpart, establishing a depth separation theorem in sample complexity. 2020 Mathematics Subject Classification Primary 68T07. Secondary 41A25, 41A30, 46E22. 1. Introduction Random feature methods have become a standard tool for scaling up kernel methods to large datasets. Since the seminal work of Rahimi and Recht [ 11 , 12 ] , a variety of random feature constructions have been proposed, giving efficient algorithms for supervised learning, regression, and classification while maintaining approximation guarantees derived from reproducing kernel Hilbert space (RKHS) theory. The key idea is to approximate a kernel K(x,x^{\prime}) by a Monte Carlo average of randomized nonlinear features of the input, thereby replacing expensive kernel evaluations by finite-dimensional linear models. Most existing analyses and applications of random features have focused on shallow models, where the function is expressed as a linear combination of random nonlinear features of the input. In parallel, the success of deep neural networks has highlighted the role of compositional structure and depth in achieving expressive and efficient representations. This has motivated a growing line of work on deep kernel learning [ 16 , 1 ] , the neural tangent kernel (NTK) [ 9 ] , and other compositional kernel constructions [ 3 , 5 , 10 ] . These approaches show that depth can fundamentally alter the geometry of the induced RKHS and thereby improve learning capacity. In this paper we develop and analyze random-kernel networks (RKNs), a multilayer generalization of random feature models. Unlike classical neural networks, where parameters are trained in every layer, our construction fixes a base kernel and generates deeper layers by deterministic composition. Each layer is defined as an RKHS induced by an integral transform of the previous kernel, while randomness enters only through Monte Carlo sampling in the outermost layer. Thus, in contrast to standard deep networks, the only trainable parameters are the outermost linear coefficients. Depth in our model refers to the compositional structure of the kernel, not to additional layers of optimization. This viewpoint is closely related to the literature on deep kernel machines [ 3 , 16 ] , randomized neural networks [ 8 , 7 ] , and compositional kernel learning [ 5 , 4 ] . However, our contribution differs in that we provide a systematic definition of multilayer random-kernel networks and a rigorous analysis of their Monte Carlo approximation properties. In particular, we show that depth can provide quantitative efficiency gains: there exist functions that can be represented compactly at depth two, but for which every depth-one approximation requires asymptotically more Monte Carlo samples. Formally, we establish a depth separation theorem in sample complexity: letting N_{\mathrm{deep}}(\epsilon) and N_{\mathrm{shallow}}(\epsilon) denote the minimal number of Monte Carlo samples needed by two-layer and one-layer random-kernel networks, respectively, to achieve squared L^{2} error at most \epsilon^{2} , we prove that there exists a depth-two function f_{2} such that \frac{N_{\mathrm{shallow}}(\epsilon)}{N_{\mathrm{deep}}(\epsilon)}\to\infty as a construction parameter grows. This gives a strict, tunable efficiency gain for depth. To our knowledge, this appears to be the first result that establishes depth separation for Monte Carlo sample complexity in kernel-based random feature models. The present setting provides a bridge between random feature methods and deep kernel constructions. On the one hand, it inherits the algorithmic simplicity of random features, since training reduces to linear regression in the outermost coefficients. On the other hand, it exhibits structural advantages of depth traditionally associated with neural networks. This makes random-kernel networks a promising mathematical model for understanding the role of depth beyond standard parametric optimization. Organization. Section 2 defines random-kernel networks and their associated RKHSs. Section 3 develops the special case of the ReLU kernel, deriving explicit formulas and a Monte Carlo approximation bound for last-layer sampling in this widely studied activation. Section 4 presents a general depth separation theorem, extending the ReLU analysis to a wide class of base kernels. 2. Compositional Kernels via Random Features We now introduce the general framework of random-kernel networks, which will serve as the foundation for the ReLU case study in Section 3 . The construction starts from a base kernel-generating function and builds deeper layers recursively by composition. Depth in this model reflects the compositional structure of the kernels, rather than additional layers of trainable parameters. Settings. Let X\subset\mathbb{R}^{d} be the input domain. Fix a measurable, bounded function K\colon\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R} . Let Z=\mathbb{R}^{d}\times\mathbb{R}\times\mathbb{R} with generic element z=\left(a,b,t\right) , and let \rho be a probability measure on Z . Define the first-layer atom and kernel by \displaystyle\psi^{\left(1\right)}_{z}\left(x\right) \displaystyle=K\left(\left\langle a,x\right\rangle+b,t\right) \displaystyle K^{\left(1\right)}\left(x,x^{\prime}\right) \displaystyle=\int_{Z}\psi^{\left(1\right)}_{z}\left(x\right)\psi^{\left(1\right)}_{z}\left(x^{\prime}\right)d\rho\left(z\right),\quad x,x^{\prime}\in X. Then K^{\left(1\right)} is positive definite (as an inner product in L^{2}\left(\rho\right) ) and determines an RKHS \mathcal{H}^{\left(1\right)} . For deeper layers we need to evaluate K^{\left(l-1\right)}\left(a,x\right) for arbitrary a\in\mathbb{R}^{d} . We therefore extend K^{\left(1\right)} to \mathbb{R}^{d}\times X by the same integral formula. Recursively, once K^{\left(l-1\right)} is defined and extended to \mathbb{R}^{d}\times X , set for l\geq 2 , \displaystyle\psi^{\left(l\right)}_{z}\left(x\right) \displaystyle=K\left(K^{\left(l-1\right)}\left(a,x\right)+b,t\right), \displaystyle K^{\left(l\right)}\left(x,x^{\prime}\right) \displaystyle=\int_{Z}\psi^{\left(l\right)}_{z}\left(x\right)\psi^{\left(l\right)}_{z}\left(x^{\prime}\right)d\rho\left(z\right),\quad x,x^{\prime}\in X. Again, K^{\left(l\right)} is positive definite and determines an RKHS \mathcal{H}^{\left(l\right)} . Each \mathcal{H}^{\left(i\right)} , i=1,\dots,l , consists of functions of the form (see e.g., [ 2 ] and [ 13 , Theorem 4.21] ) (2.1) f\left(x\right)=\int_{Z}c\left(z\right)\psi^{\left(i\right)}_{z}\left(x\right)d\rho\left(x\right),\quad c\in L^{2}\left(\rho\right), with norm (2.2) \left\|f\right\|_{\mathcal{H}^{\left(i\right)}}=\inf\left\{\left\|c\right\|_{L^{2}\left(\rho\right)}:f=\int c\psi^{\left(i\right)}_{z}d\rho\right\}. A depth- l random-kernel network is defined as follows: sample i.i.d. parameters z_{j}=\left(a_{j},b_{j},t_{j}\right)\sim\rho and set f_{N}\left(x\right)=\sum^{N}_{j=1}\alpha_{j}\psi^{\left(l\right)}_{z_{j}}\left(x\right),\quad x\in X. In this model, only the coefficients \alpha_{j} in the outermost layer are trained. The inner layers appear through deterministic integral transforms that define the kernels K^{\left(l\right)} . This is therefore different from the traditional notion of a multilayer neural network, where weights in every layer are optimized. Here the notion of depth refers to the compositional structure of the kernel rather than to additional layers of trainable parameters. The benefit of this construction is that certain compositional target functions can be represented with substantially smaller outermost coefficient norms (see \left\|c\right\|_{L^{2}\left(\rho\right)} in ( 2.1 )–( 2.2 )) than is possible in the single-layer case, leading to provable efficiency gains in the number of random features required for approximation. 3. Depth Separation on a Slice: A Two-Layer ReLU Example This section treats a concrete two-layer ReLU case to illustrate the depth-efficiency phenomenon on a one-dimensional slice. The next section states and proves a general depth- l theorem under broader assumptions. Our strategy is to design a specific two-layer function that is inherently compositional and then analyze what is required to approximate it using both a deep (two-layer) and a shallow (one-layer) random-kernel network. To make the analysis tractable, we focus on the approximation error along a specific one-dimensional slice of the input space, x=sv . This is sufficient to establish the desired separation; if a shallow model requires a large number of samples to approximate the function on this single line, its sample complexity for the function over the entire domain must also be large. The argument proceeds in three main steps. First, we construct a “steep” two-layer target function f_{2} , whose steepness is controlled by a