A duality framework for generalization analysis of random feature models
  and two-layer neural networks
We consider the problem of learning functions in the $\mathcal{F}_{p,\pi}$
and Barron spaces, which are natural function spaces that arise in the
high-dimensional analysis of random feature models (RFMs) and two-layer neural
networks. Through a duality analysis, we reveal that the approximation and
estimation of these spaces can be considered equivalent in a certain sense.
This enables us to focus on the easier problem of approximation and estimation
when studying the generalization of both models. The dual equivalence is
established by defining an information-based complexity that can effectively
control estimation errors. Additionally, we demonstrate the flexibility of our
duality framework through comprehensive analyses of two concrete applications.
  The first application is to study learning functions in $\mathcal{F}_{p,\pi}$
with RFMs. We prove that the learning does not suffer from the curse of
dimensionality as long as $p>1$, implying RFMs can work beyond the kernel
regime. Our analysis extends existing results [CMM21] to the noisy case and
removes the requirement of overparameterization.
  The second application is to investigate the learnability of reproducing
kernel Hilbert space (RKHS) under the $L^\infty$ metric. We derive both lower
and upper bounds of the minimax estimation error by using the spectrum of the
associated kernel. We then apply these bounds to dot-product kernels and
analyze how they scale with the input dimension. Our results suggest that
learning with ReLU (random) features is generally intractable in terms of
reaching high uniform accuracy.
Hongrui Chen, Jihao Long, Lei Wu
A duality framework for generalization analysis of random feature models and two-layer neural networks

###### Abstract

We consider the problem of learning functions in the \(\mathcal{F}_{p,\pi}\) and Barron spaces, which are natural function spaces that arise in the high-dimensional analysis of random feature models (RFMs) and two-layer neural networks. Through a duality analysis, we reveal that the approximation and estimation of these spaces can be considered equivalent in a certain sense. This enables us to focus on the easier problem of approximation and estimation when studying the generalization of both models. The dual equivalence is established by defining an information-based complexity that can effectively control estimation errors. Additionally, we demonstrate the flexibility of our duality framework through comprehensive analyses of two concrete applications.

* The first application is to study learning functions in \(\mathcal{F}_{p,\pi}\) with RFMs. We prove that the learning does not suffer from the curse of dimensionality as long as \(p>1\), implying RFMs can work beyond the kernel regime. Our analysis extends existing results [10] to the noisy case and removes the requirement of overparameterization.
* The second application is to investigate the learnability of reproducing kernel Hilbert space (RKHS) under the \(L^{\infty}\) metric. We derive both lower and upper bounds of the minimax estimation error by using the spectrum of the associated kernel. We then apply these bounds to dot-product kernels and analyze how they scale with the input dimension. Our results suggest that learning with ReLU (random) features is generally intractable in terms of reaching high uniform accuracy.

## 1 Introduction

One of the fundamental problems in theoretical machine learning is to understand how certain high-dimensional functions can be learned _efficiently_ using machine learning models [1, 1] such as neural networks and random feature models. Denote by \(\mathcal{X}\subset\mathbb{R}^{d}\) the input domain and \(\mathcal{F}\) the function class of interest. We say that \(\mathcal{F}\) can be learned efficiently if both the approximation error and estimation error scale polynomially with the input dimension \(d\). Otherwise, the learning is said to suffer from or exhibit the _curse of dimensionality_ (CoD) [1].

It is well-known that learning traditional function spaces such as Sobolev and Besov spaces suffers from the CoD, regardless of the machine learning models used [23, 24]. Analyses with these spaces cannot explain the success of machine learning in solving high-dimensional problems. To address this, it is crucial to identify the appropriate function spaces for a given machine learning model such that the functions can be learned efficiently using that model [1, 1].
This can provide insight into the model's strengths and limitations when dealing with high-dimensional data. This paper focuses on this issue for three popular machine learning models: kernel methods, random feature models, and two-layer neural networks.

Kernel methods are a class of methods using the hypothesis class: \(\{\sum_{i=1}^{n}\alpha_{i}k(x_{i},\cdot):\alpha\in\mathbb{R}^{n}\}\), where \(\{x_{i}\}_{i=1}^{n}\) are training data and \(k:\mathcal{X}\times\mathcal{X}\mapsto\mathbb{R}\) is a kernel function. The popular function space used in kernel method analysis is the reproducing kernel Hilbert space (RKHS) [1], denoted by \(\mathcal{H}_{k}\). RKHS is favored for two main reasons. First, it can be learned efficiently with kernel methods in high dimensions, as demonstrated in studies such as [1, 15]. Second, the Hilbert structure and reproducing property of RKHS provide a rich set of mathematical tools that make analysis easier. For instance, the use of RKHS allows for the representation of functions as inner products with respect to the kernel, i.e., \(f(x)=\langle f,k(x,\cdot)\rangle_{\mathcal{H}_{k}}\), enabling the application of techniques from functional analysis.

Neural networks are another class of models which have achieved remarkable success in solving high-dimensional problems [14]. However, it remains unclear which high-dimensional functions can be efficiently learned using them. In this paper, we focus on two-layer neural networks:

\[f(x;\theta)=\sum_{j=1}^{m}a_{j}\phi(x,v_{j}), \tag{1}\]

where \(\phi:\mathcal{X}\times\mathcal{V}\mapsto\mathbb{R}\) is a feature function and \(\theta=\{(a_{j},v_{j})\}_{j=1}^{m}\) are the parameters to be learned. The feature function is typically the form of \(\phi(x,v)=\sigma(v^{T}x)\), where \(\sigma:\mathbb{R}\mapsto\mathbb{R}\) is a nonlinear activation function.

The high-dimensional analysis of two-layer neural networks dates back to the pioneer works by Andrew Barron [1, 15]. In these papers, Barron defined the spectral Barron space [13], which consists of functions that satisfy \(C_{f}=\int(1+\|\xi\|)|\hat{f}(\xi)|\,\mathrm{d}\xi<\infty\), and proved that these functions can be efficiently learned using two-layer neural networks. Following Barron's work, [1, 14] defined variation spaces and [1] reformulated these spaces using integral representations, which were denoted by \(\mathcal{F}_{1}\). More recently, [1] provided a probabilistic interpretation of Barron's work and defined the Barron spaces, which are an infinite union of a family of RKHSs. These spaces played a critic role in understanding the capabilities and limitations of two-layer neural networks in high dimensions.

Random feature models (RFMs) are another type of closely related models that have the same form as Equation (1), but with the weights \(\{v_{j}\}_{j=1}^{m}\) being _i.i.d._ samples drawn from a fixed distribution \(\pi\in\mathcal{P}(\mathcal{V})\). In RFMs, the features are predetermined, and only the outer coefficients are learnable. When the \(\ell_{2}\) norm of the coefficients is penalized, RFMs are equivalent to kernel methods with kernel \(\hat{k}_{m}(x,x^{\prime})=\frac{1}{m}\sum_{j=1}^{m}\phi(x,v_{j})\phi(x^{\prime},v_{j})\) according to the representer theorem [12]. It is important to note that as \(m\to\infty\), the law of large numbers (LLN) implies that

\[\hat{k}_{m}(x,x^{\prime})\to k_{\pi}(x,x^{\prime}):=\int_{\mathcal{V}}\phi(x,v )\phi(x^{\prime},v)\,\mathrm{d}\pi(v). \tag{2}\]

Hence RFMs are often viewed as a Monte-Carlo approximation of kernel methods with kernel \(k_{\pi}\)[10], and consequently, most theoretical analyses of RFMs only consider target functions in the associated RKHS \(\mathcal{H}_{k_{\pi}}\)[11, 10, 12]. However, it should be stressed that RFMs are not kernel methods if the \(\ell_{p}\) norm of coefficients is penalized with \(p<2\)[13, 14, 15]. Recently, RFMs have been also found useful for understanding neural networks [1, 1, 12, 13, 14].
### Our contributions

In this paper, we study the learning of the \(\mathcal{F}_{p,\pi}\) and Barron spaces, whose definitions are motivated by the high-dimensional analysis of RFMs and two-layer neural networks, respectively. Consider a RFM with infinitely many features: \(f_{a}=\int_{\mathcal{V}}a(v)\phi(\cdot,v)\,\mathrm{d}\pi(v)\), where the parameters are the coefficient function \(a(\cdot)\). For any \(p\geq 1\), \(\mathcal{F}_{p,\pi}\) is defined by

\[\mathcal{F}_{p,\pi}:=\{f_{a}\,:\,\|a\|_{L^{p}(\pi)}<\infty\},\qquad\|f\|_{ \mathcal{F}_{p,\pi}}=\inf_{f_{a}=f}\|a\|_{L^{p}(\pi)}. \tag{3}\]

The Barron space \(\mathcal{B}\) is given by

\[\mathcal{B}=\cup_{\pi\in\mathcal{P}(\mathcal{V})}\mathcal{F}_{2,\pi}. \tag{4}\]

These spaces have been widely adopted to analyze RFMs and two-layer neural networks [1, 2, 1, 16] in high dimensions. In particular, [11] proved \(\mathcal{F}_{2,\pi}=\mathcal{H}_{k_{\pi}}\), where the kernel \(k_{\pi}\) is given by (2); therefore, studying \(\mathcal{F}_{p,\pi}\) is also highly relevant for understanding kernel methods.

In this paper, we take a duality perspective to provide a unified analysis of the \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) spaces. This approach enables us to gain a more general and comprehensive understanding of the properties of these spaces, and gain insights into their relevance for understanding kernel methods, two-layer neural networks, and RFMs.

The duality property.By exploiting the Banach structure of \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\), we establish a dual equivalence between the approximation and estimation for learning functions in \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\). To put it simply, our major result for the case of \(\mathcal{F}_{p,\pi}\) can be informally stated as follows

_The \(L^{q}(\rho)\) estimation of \(\mathcal{F}_{p,\pi}\) is equivalent to the \(L^{p^{\prime}}(\pi)\) approximation of \(\mathcal{F}_{q^{\prime},\rho}\),_

where \(p^{\prime},q^{\prime}\) denote the Holder conjugates of \(p,q\), satisfying \(1/p+1/p^{\prime}=1,1/q+1/q^{\prime}=1\). An analogous dual equivalence also holds for the Barron space \(\mathcal{B}\). This duality property enables us to concentrate on analyzing the easier problem between approximation and estimation, leading to a unified analysis of learning in these spaces under various metrics.

The information-based complexity.To establish the aforementioned dual equivalence, we introduce an _information-based complexity_(\(I\)-complexity) that can effectively control the (minimax) estimation errors in various settings. A similar complexity has been utilized in approximation theory to study optimal interpolations on deterministically obtained clean data [14]. However, in statistical learning settings, data are typically randomly sampled from a distribution, and the model may not necessarily interpolate data due to the presence of noise. To address this issue, we modify the definition of \(I\)-complexity to make it more appropriate for this setting. The \(I\)-complexity might be of independent interest and could potentially be applied beyond the analysis of the \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) spaces. Nonetheless, we leave the exploration of its potential applications for future work.

Applications.Our duality framework allows us to simplify the proofs and strengthen the conclusions of many existing results. We illustrate this by providing two specific applications:

* _Random feature learning beyond kernel regime._ First, we extend the result in [1, Proposition 1] by showing that the unit ball of \(\mathcal{F}_{p,\pi}\) can be uniformly approximated by random features, where uniformity means that the choice of random weights \(v_{1},\ldots,v_{m}\) is independent of target functions. In contrast to [1], our result is not restricted to the case of \(\mathcal{F}_{2,\pi}\) and the proof is also much simpler. Next, we provide a comprehensive analysis of learning \(\mathcal{F}_{p,\pi}\) functions using RFMs. Our analysis shows that both the sample and parameter complexities
scale with the input dimension \(d\) polynomially, as long as \(p>1\). This result suggests that RFMs can efficiently learn functions that are not necessarily contained in RKHS.
* \(L^{\infty}\) _learnability of RKHS_. We consider the learning of functions in RKHS under the \(L^{\infty}\) metric: \(\|\hat{f}-f^{*}\|_{\infty}=\sup_{x\in\mathcal{X}}|\hat{f}(x)-f^{*}(x)|\), where \(\hat{f},f^{*}\) denote the learned model and the target function, respectively. This \(L^{\infty}\) learnability is crucial for understanding the performance of kernel methods and neural networks in safety- and security-critical scenarios. By exploiting the dual equivalence, we show that the \(L^{\infty}\) estimation of a RKHS (i.e., \(\mathcal{F}_{2,\pi}\)) is equivalent to the \(L^{2}\) approximation of the Barron space \(\mathcal{B}\) with random features. To bound the error of the latter, we adopt the spectral-based approach developed in [10]. We derive both lower and upper bounds on the \(L^{\infty}\) minimax errors based on the kernel spectrum. In particular, we examine how the \(L^{\infty}\) learnability depends on the input dimension \(d\) for dot-product kernels of the form \(k(x,x^{\prime})=\mathbb{E}_{v\sim\tau_{d-1}}[\sigma(v^{T}x)\sigma(v^{T}x^{ \prime})]\). Specifically, we prove
* For non-smooth activation functions, such as ReLU, the minimax errors grow exponentially with the input dimension \(d\);
* For sufficiently smooth activation functions, the error scales with \(d\) only polynomially. Note that dot-produce kernels arise naturally in studying RFMs [14] and neural networks [13] and therefore, the above results not only apply to kernel methods but also provide insights into RFMs and neural networks. One immediate implication is that \(L^{\infty}\) learning with ReLU random features/neural networks is subject to the CoD, although the \(L^{2}\) learning is not [1, 1].

The above examples demonstrate the versatility of our duality framework, and we believe it has the potential to be applied in other contexts and settings beyond these specific examples.

### Related works

Duality of RFMs and neural networks.In [1], a dual formulation for training energy-based models with overparameterized two-layer neural networks was provided. In contrast, we focus on supervised learning and generalization analysis. We note that there is a concurrent work [12], which provides fine-grained structure characterizations of the \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) spaces under the framework of reproducing kernel Banach space (RKBS) [11]. We instead establish the dual equivalence between approximation and estimation of these spaces.

Random feature learning.The early works [14, 14] focused on the approximation of RFMs for functions within the associated RKHS. [1] provided a fine-grained analysis of the approximation error by using the corresponding covariance operator. In contrast, we offer a duality analysis, which provides simpler proofs and applies to target functions beyond the RKHS.

Note that [13] also considered the problem of learning \(\mathcal{F}_{p,\pi}\). However, their analysis only considered minimum-norm estimators under the noiseless case and is limited to a highly overparameterized regime with \(m\gg(n\log n)^{2}\), where \(m\) is the number of features and \(n\) is the sample size. In contrast, our analysis in Section 6 does not require overparameterization and is applicable to both noisy and noiseless cases. This is made possible by our duality framework.

\(L^{\infty}\) learnability of RKHS and neural networks.The \(L^{\infty}\) learning of RKHS was first studied in [17] for the case of deterministic samples, where both upper and lower bounds are derived by using the kernel spectrum. [13] improved the upper bound by allowing samples to
be randomly drawn from an input distribution. In this paper, we show that similar bounds can be easily derived from our duality framework and in particular, we extends the lower bound to the noisy case, which is more common in machine learning. Additionaly, we improve the upper bound for dot-product kernels in two aspects. First, our upper bound (Theorem 22) is obtained by using RFMs, while [12, 13] used the eigenfunctions of the associated kernel as the fixed feature. Second, [12, 13] required the uniform boundedness of eigenfunctions, but the eigenfunctions of dot-product kernels, which are spherical harmonics, do no satisfy this condition.

More recently, [1] showed that the \(L^{\infty}\) estimation of deep neural networks suffers from the CoD. Our analysis shows a stronger result: actually, the CoD occurs for the much simpler RFMs if the activation function is non-smooth, such as ReLU.

Connection with [11]We acknowledge that [11] applied a similar approach to analyze reinforcement learning by defining a quantity called perturbation complexity. Specifically, they analyzed the case where the reward function comes from a RKHS and as a result, their analysis mainly focused on the \(\mathcal{F}_{2,\pi}\) space. In contrast, we focus on supervised learning setup and we provide a comprehensive analysis of the \(\mathcal{F}_{p,\pi}\) spaces for all \(p\geq 1\) and the Barron spaces.

### Organization

In Section 2, we clarify notations and preliminaries. In Section 3, we define the information-based complexity and show how it controls various estimation errors of learning a function class. In Section 4, we define the \(\mathcal{F}_{p,\pi}\) and Barron spaces, which will play critical roles in our duality analysis. In Section 5, we present the dual equivalence between estimation and approximation for learning \(\mathcal{F}_{p,\pi}\) and Barron spaces. Section 6 and 7 present two applications of our duality framework: Random feature learning beyond kernel regime and \(L^{\infty}\) learning of RKHS.

## 2 Preliminaries

Notations.Let \(\Omega\) be a subset of a Euclidean space. We denote by \(\mathcal{P}(\Omega)\) the set of probability measures on \(\Omega\) and \(\mathcal{M}(\Omega)\) the space of signed Radon measures equipped with the total variation norm \(\|\mu\|_{\mathcal{M}(\Omega)}=\|\mu\|_{\mathrm{TV}}\). Given \(z_{1},\ldots,z_{n}\in\Omega\), denote by \(\hat{\rho}_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{z_{i}}\) the empirical distribution. For any \(\rho\in\mathcal{P}(\Omega)\), let \(\|\cdot\|_{p,\rho}\) be the \(L^{p}(\rho)\) norm. When \(p=2\), we write \(\|\cdot\|_{\rho}=\|\cdot\|_{2,\rho}\) for convenience and let \(\langle f,g\rangle_{\rho}=\int f(x)g(x)\,\mathrm{d}\rho(x)\) for any \(f,g\in L^{2}(\rho)\). Let \(C_{0}(\Omega)\) the space of continuous functions vanishing at infinity equipped with the uniform norm(\(L^{\infty}\) norm) \(\|g\|_{C_{0}(\mathcal{X})}:=\|g\|_{\infty}=\sup_{x\in\mathcal{X}}|g(x)|\). We shall occasionally use \(L^{\infty}\) and \(\|\cdot\|_{\infty}\) to denote \(\|\cdot\|_{C_{0}(\mathcal{X})}\), which is different from \(L^{\infty}(\rho)\). One should not confuse \(L^{\infty}\) and \(L^{\infty}(\rho)\). For any vector \(v\), denote by \(\|v\|_{p}=\left(\sum_{i}|v_{i}|^{p}\right)^{1/p}\) the \(\ell^{p}\) norm. When \(p=2\), we drop the subscript for simplicity.

For any \(p\in[1,\infty)\), denote by \(p^{\prime}\) the Holder conjugate saisifying \(\frac{1}{p}+\frac{1}{p^{\prime}}=1\). For a normed vector space \(\mathcal{F}\), let \(\mathcal{F}(r):=\{f\in\mathcal{F}:\|f\|_{\mathcal{F}}\leq r\}\) be the ball of radius \(r\). Let \(\mathbb{S}^{d-1}=\{x\in\mathbb{R}^{d}:\|x\|_{2}=1\}\) and \(\tau_{d-1}=\mathrm{Unif}(\mathbb{S}^{d-1})\). We use \(a\lesssim b\) to mean \(a\leq Cb\) for an absolute constant \(C>0\) and \(a\gtrsim b\) is defined analogously. We use \(a\asymp b\) if there exist absolute constants \(C_{1},C_{2}>0\) such that \(C_{1}b\leq a\leq C_{2}b\).

Rademacher complexity.Given \(x_{1},x_{2},\ldots,x_{n}\in\mathcal{X}\), the (empirical) Rademacher complexity of a function class \(\mathcal{F}\) is defined by

\[\widehat{\mathrm{Rad}}_{n}(\mathcal{F})=\mathbb{E}_{\xi_{1},\ldots,\xi_{n}}[ \sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})\xi_{i}], \tag{5}\]
where \(\xi_{1},\ldots,\xi_{n}\) are _i.i.d._ Rademacher random variables, i.e., \(\mathbb{P}(\xi_{i}=1)=\mathbb{P}(\xi_{i}=-1)=1/2\). In particular, we will use the following classical theorem to bound the gap between an empirical quantity and its population counterpart.

Mercer decomposition.Before presenting our results, we first recall some basic facts about the eigen decomposition of a kernel. For any kernel \(k:\mathcal{X}\times\mathcal{X}\mapsto\mathbb{R}\), the associated integral operator \(\mathcal{T}_{k}:L^{2}(\gamma)\mapsto L^{2}(\gamma)\) is given by \(\mathcal{T}_{k}f=\int k(\cdot,x)f(x)\,\mathrm{d}\gamma(x).\) When \(k\) is continuous and \(\mathcal{X}\) is compact, the Mercer's theorem guarantees the existance of eigen decomposition of \(k\): \(k(x,x^{\prime})=\sum_{i=1}^{\infty}\mu_{i}e_{i}(x)e_{i}(x^{\prime})\). Here \(\{\mu_{i}\}_{i=1}^{\infty}\) are the eigenvalues in a decreasing order and \(\{e_{i}\}_{i=1}^{\infty}\) are the orthonormal eigenfunctions satisfying \(\int e_{i}(x)e_{j}(x)\,\mathrm{d}\gamma(x)=\delta_{i,j}\). Note that the decomposition depends on the input distribution \(\gamma\) and when needed, we will denote by \(\mu_{i}^{k,\gamma}\) the \(i\)-th eigenvalue to explicitly emphasize the influence of \(k\) and \(\gamma\). We are also interested in the following quantity:

\[\Lambda_{k,\gamma}(m)=\sqrt{\sum_{i=m+1}^{\infty}\mu_{i}^{k,\gamma}}, \tag{6}\]

which will be used in Section 7 to bound the \(L^{\infty}\) learnability of RKHS. We refer to [20, Section 12.3] for more details about Mercer's decomposition.

## 3 The Information-based complexity

Our generalization analysis relies on the information-based complexity (\(I\)-complexity) proposed in [17]. The \(I\)-complexity of a function class \(\mathcal{F}\) defined in [17, Remark 1.3.4] is

\[I_{n}(\mathcal{F})=\inf_{x_{1},\ldots,x_{n}\in\mathcal{X}}\sup_{f\in\mathcal{F },f(x_{i})=0}\|f\|_{\infty}. \tag{7}\]

Intuitively speaking, \(I_{n}(\mathcal{F})\) quantifies the complexity of a function class with the minimax \(L^{\infty}\) norm of functions in \(\mathcal{F}\) that interpolate the zero function at \(n\) points. [17] showed that \(I_{n}(\mathcal{F})\) can control the minimax error of approximating \(\mathcal{F}\) with the information of only \(n\) data points.

However, the definition (7) cannot be directly applied to analyze ML models. First, the input data in machine learning are often randomly sampled from an input distribution, while \(I_{n}(\mathcal{F})\) measures the complexity with the worst case over any \(n\) data points. Second, the definition only considers the interpolation regime, while it is often prefered in machine learning that our models do not interpolate data as it may cause the _overfitting_ issue. This is particularly the case when data are noisy. To resolve these issues, we define the following modified \(I\)-complexity.

**Definition 1** (\(I\)-complexity).: Let \(\mathcal{F}\) be a set of functions, \(\nu\in\mathcal{P}(\mathcal{X})\) be a probability distribution over \(\mathcal{X}\), and \(\|\cdot\|_{\mathcal{M}}\) be a norm used to measure prediction errors. The \(I\)-complexity of \(\mathcal{F}\) with respect to the distribution \(\nu\) is defined as

\[I_{\nu}(\mathcal{F},\mathcal{M},\epsilon)=\sup_{f\in\mathcal{F},\,\|f\|_{ \nu}\leq\epsilon}\|f\|_{\mathcal{M}}. \tag{8}\]

The above modification makes the \(I\)-complexity useful for the generalization analysis in machine learning as it includes both the input distribution information and include the non-interpolate estimators. Next, we will show that how this complexity can bound estimation errors.
**Remark 2**.: _It should be noted that Definition 1 allows \(\nu\) to be a general distribution to measure fitting errors and \(\mathcal{M}\) to be a general norm of measuring prediction errors. In particular, one may choose \(\nu=\hat{\rho_{n}}=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}\), which is the fitting error on the training data. One can also choose \(\nu=\rho\), yielding a distribution-dependent complexity \(\mathcal{I}_{\rho}(\mathcal{F},\mathcal{M},\epsilon)\). We will show that this quantity provides a lower bound of the minimax error of estimating \(\mathcal{F}\) in noisy case. It is worth noting that the flexibility of allowing to measure fitting and prediction errors with different metrics might be also useful for analyzing the problem of out-of-distribution generalization [21] and reinforcement learning [11, 12]._

### Bounding estimation errors.

Consider the supervised learning with data \(\{(x_{i},y_{i}=f(x_{i}))\}_{i=1}^{n}\). Suppose that \(\mathcal{F}\) is a Banach space of functions over \(\mathcal{X}\) and \(f\in\mathcal{F}(1)\). Consider an estimator \(\hat{f}\in\mathcal{F}(1)\) with the empirical error satisfying

\[\left(\frac{1}{n}\sum_{i=1}^{n}(\hat{f}(x_{i})-y_{i})^{2}\right)^{1/2}=\|\hat {f}-f\|_{\hat{\rho}_{n}}\leq\epsilon.\]

Then, the population error of \(\hat{f}\) can be bounded by the \(I\)-complexity:

\[\|\hat{f}-f\|_{\mathcal{M}}\leq\sup_{\|g\|_{\mathcal{F}}\leq 2,\,\|g\|_{ \hat{\rho}_{n}}\leq\epsilon}\|g\|_{\mathcal{M}}=2I_{\hat{\rho}_{n}}(\mathcal{ F}(1),\mathcal{M},\epsilon/2), \tag{9}\]

where the first step is because \(\|\hat{f}-f\|_{\mathcal{M}}\leq\|\hat{f}\|_{\mathcal{M}}+\|f\|_{\mathcal{M}}\leq 2\).

Next, we further show that the \(I\)-complexity can also bound the minimax estimation errors. We call each measurable map from \((\mathcal{X}\times\mathbb{R})^{n}\) to \(\mathcal{F}\) an estimator and denote by \(\mathcal{A}_{n}\) the set of all estimators: \((\mathcal{X}\times\mathbb{R})^{n}\mapsto\mathcal{F}\). For an estimator \(T_{n}\), the estimation error of \(T_{n}\) is given by

\[\|T_{n}(\{(x_{i},y_{i})\}_{i=1}^{n})-f\|_{\mathcal{M}}.\]

The following two lemmas show that the \(I\)-complexity defined in Definition 1 can control the minimax error of learning a set of functions. Here we only state the results and the proofs can be found in Appendix A.

The sample-dependent minimax error.For fixed input data \(x_{1},\cdots,x_{n}\) and noiseless output, the sample-dependent minimax estimation error is given by

\[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{F}}\leq 1}\|T_{n}(\{(x_ {i},f(x_{i}))\}_{i=1}^{n})-f\|_{\mathcal{M}}. \tag{10}\]

In this case, the worst-case error may depend on the samples \(x_{1},x_{2},\ldots,x_{n}\) and this error measures how much we can extract from the specific \(n\) samples in the minimax sense. The following proposition shows that this minimax estimation error can be quantified by the \(I\)-complexity \(I_{\hat{\rho}_{n}}\):

**Proposition 3**.: _For any \(x_{1},\cdots,x_{n}\in\mathcal{X}\), we have_

\[I_{\hat{\rho}_{n}}(\mathcal{F}(1),\mathcal{M},0)\leq\inf_{T_{n}\in\mathcal{A}_ {n}}\sup_{\|f\|_{\mathcal{F}}\leq 1}\|T(\{(x_{i},f(x_{i}))\}_{i=1}^{n})-f\|_{ \mathcal{M}}\leq 2I_{\hat{\rho}_{n}}(\mathcal{F}(1),\mathcal{M},0).\]

It is worth noting that the above result holds for any \(x_{1},x_{2},\ldots,x_{n}\in\mathcal{X}\), which are not necessary to be _i.i.d._ samples drawn from an input distribution.
The distribution-dependent minimax error.Suppose that the training data \(S=\{(x_{i},y_{i})\}_{i=1}^{n}\) are independently generated by \(x_{i}\sim\rho\), \(y_{i}=f(x_{i})+\xi_{i}\) with \(\xi_{i}\sim\mathcal{N}(0,\varsigma^{2})\) being the Gaussian noise. Consider the following minimax error

\[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{F}}\leq 1}\mathbb{E}\,\|T_{n}( \{(x_{i},f(x_{i})+\xi_{i})\}_{i=1}^{n})-f\|_{\mathcal{M}}, \tag{11}\]

where the expection is taken with respect to the sampling of \(S\). This minimax error is the common choice in statistical learning setup (see [26, Section 15]). In this definition, the worst case only depends on the distribution instead of specific samples. The following lemma shows that the complexity \(I_{\rho}\) with \(\epsilon=\varsigma/\sqrt{n}\) gives a lower bound of the minimax error (11):

**Proposition 4**.: _We have_

\[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{F}}\leq 1}\mathbb{E}\,\|T _{n}(\{(x_{i},f(x_{i})+\xi_{i})\}_{i=1}^{n})-f\|_{\mathcal{M}}\geq I_{\rho} \left(\mathcal{F}(1),\mathcal{M},\frac{\varsigma}{\sqrt{n}}\right)\]

Note that in some specific cases, the \(I\)-complexity also provides an upper bound of the distribution-dependent minimax error. We refer to Section 7 for details.

**Remark 5**.: _What we discuss above only considers the estimation part since the output of estimator is in the target space \(\mathcal{F}\). In other words, for any estimator in \(A_{n}\), the approximation error is exactly zero. However, in practice, an estimate \(\hat{f}\) may live in the hypothesis space \(\mathcal{H}\), which can be different from \(\mathcal{F}\). In such a case, there may exist approximation error because of the difference between \(\mathcal{H}\) and \(\mathcal{F}\). In Section 5, we establish that for various function spaces of interest in studying RFMs and two-layer neural networks, the \(I\)-complexity also controls the approximation error._

## 4 The \(\mathcal{F}_{p,\pi}\) and Barron spaces

Let \(\phi:\mathcal{X}\times\mathcal{V}\to\mathbb{R}\) be a general parametric feature map and \(\mathcal{X}\) and \(\mathcal{V}\) denote the input and weight space, respectively. A typical example of feature map is \(\phi(x,v)=\sigma(v^{T}x)\), which arises naturally in analyzing neural networks and random feature models. Here \(\sigma:\mathbb{R}\mapsto\mathbb{R}\) is a nonlinear activation function. In this section, we define some function spaces induced by \(\phi\), which will be utilized in our subsequent duality analysis.

We first define the function spaces for random feature models.

**Definition 6**.: Let \(\pi\in\mathcal{P}(\mathcal{V})\) be a probability distribution over the weight space. For \(1\leq p\leq\infty\), the \(\mathcal{F}_{p,\pi}\) space on \(\mathcal{X}\) is defined as

\[\mathcal{F}_{p,\pi}:=\left\{f=\int_{\mathcal{V}}a(v)\phi(\cdot,v)\,\mathrm{d} \,\pi(v):\,a\in L^{p}(\pi)\right\},\]

equipped with the norm

\[\|f\|_{\mathcal{F}_{p,\pi}}=\inf_{a\in A_{f}}\|a\|_{p,\pi},\quad\text{where}\, A_{f}=\left\{a\in L^{p}(\pi):\,f=\int_{\mathcal{V}}a(v)\phi(\cdot,v)\,\mathrm{d} \,\pi(v)\right\}. \tag{12}\]

In this definition, we consider functions admitting the integral representation with respect to the feature map \(\phi\). For a given \(f\), the associate \(a(\cdot)\) will be called the representation of \(f\). Note that the representations may not be unique. Hence, taking infimum in (12) ensures the norm of \(f\) to be measured using the optimal representation. In addition, this makes the \(\mathcal{F}_{p,\pi}\) well-defined in the sense that it is independent of the choice of representation.

Some observations go as follows.
* It follows trivially from the Holder's inequality that \[\mathcal{F}_{\infty,\pi}\subset\mathcal{F}_{p,\pi}\subset\mathcal{F}_{q,\pi} \subset\mathcal{F}_{1,\pi},\quad\text{ if }\,p\geq q.\] (13)
* The \(\mathcal{F}_{p,\pi}\) space provides a natural setting to study the approximation power of RFMs. Specifically, if \(v_{j}\stackrel{{ iid}}{{\sim}}\pi\) for \(j=1,\ldots,m\), then the law of large numbers (LLN) implies that as \(m\to\infty\), \[\frac{1}{m}\sum_{j=1}^{m}a_{j}\phi(x,v_{j})\to\int_{\mathcal{V}}a(v)\phi(x,v) \,\mathrm{d}\pi(v)\] and the covergence/approximation rate is determined by the \(L^{p}(\pi)\) norm of \(a(\cdot)\). In other words, the \(\mathcal{F}_{p,\pi}\) norm of \(f\) controls the rate of approximating \(f\) with RFMs. While existing works on RFMs have focused on the case of \(p=2\), it is possible to obtain similar approximation rates for all \(p\in(1,\infty]\) by using the Marcinkiewicz-Zygmund-type LLN [11, Theorem 2.5.8]. More details can be found in Section 6.

We draw attention to the case where \(p=2\), for which [10] proved \(\mathcal{F}_{2,\pi}\) is an RKHS:

\[\mathcal{F}_{2,\pi}=\mathcal{H}_{k_{\pi}},\quad\text{ with }\quad k_{\pi}(x,x^{ \prime}):=\int_{\mathcal{V}}\phi(x,v)\phi(x^{\prime},v)\,\mathrm{d}\,\pi(v). \tag{14}\]

Furthermore, the converse is also true: any RKHS can be represented as \(\mathcal{F}_{2,\pi}\), as shown in the following lemma.

**Lemma 7**.: _If a kernel \(k\) has a finite trace, i.e., \(\int_{\mathcal{X}}k(x,x)\,\mathrm{d}\,\rho(x)<\infty\), then there exists a weight probability space \((\mathcal{V},\pi)\) and feature function \(\phi:\mathcal{X}\times\mathcal{V}\mapsto\mathbb{R}\) such that_

\[k(x,x^{\prime})=k_{\pi}(x,x^{\prime}):=\int_{\mathcal{V}}\phi(x,v)\phi(x^{ \prime},v)\,\mathrm{d}\,\pi(v).\]

Proof.: By Mercer's decomposition: \(k(x,x^{\prime})=\sum_{j=1}^{\infty}\lambda_{j}e_{j}(x)e_{j}(x^{\prime})\), where \((e_{j})_{j\geq 1}\) are a set of orthonormal basis in \(L^{2}(\rho)\). Since \(\sum_{j=1}^{\infty}\lambda_{j}=\int_{\mathcal{X}}k(x,x)\,\mathrm{d}\,\rho(x)<\infty\), we can choose \(\mathcal{V}=\mathbb{N}^{+}\) and define a probability measure on \(\mathbb{N}_{+}\) by \(\pi(j)=\frac{\lambda_{j}}{\sum_{i}\lambda_{i}}\). Let \(\phi(x,j)=\sqrt{\sum_{i}\lambda_{i}}e_{j}(x)\) for \(j\in\mathbb{N}_{+}\). Then, \(k(x,x^{\prime})=\int_{\mathbb{N}_{+}}\phi(x,j)\phi(x^{\prime},j)\,\mathrm{d} \,\pi(j)\). 

We now turn to define the function space for studying two-layer neural networks.

**Definition 8** (Barron space).: Given a feature map \(\phi:\mathcal{X}\times\mathcal{V}\to\mathbb{R}\) such that \(\phi(x,\cdot)\in C_{0}(\mathcal{V})\) for any \(x\in\mathcal{X}\), we define the Barron space \(\mathcal{B}\) on \(\mathcal{X}\) as

\[\mathcal{B}:=\left\{f=\int_{\mathcal{V}}\phi(\cdot,v)\,\mathrm{d}\,\mu(v):\, \mu\in\mathcal{M}(\mathcal{V})\right\},\]

equipped with the norm

\[\|f\|_{\mathcal{B}}=\inf_{\mu\in M_{f}}\|\mu\|_{\mathrm{TV}},\quad\text{where }M_{f}=\left\{\mu\in\mathcal{M}(\mathcal{V}):\,f=\int_{\mathcal{V}}\phi(\cdot,v)\,\mathrm{d}\,\mu(v)\right\}. \tag{15}\]
The definition above, originally proposed in [11], is equivalent to the variation-based definition used in [1, 1, 12, 13]. When \(\phi(x,v)=\max(v^{\top}x,0)\), it is also equivalent to the moment-based definition proposed in [1, 1]. All of these definitions are somehow equivalent [1, 13]. In our duality analysis, we will specifically adopt the above Radon measure-based definition as we relies on the fact that \(\mathcal{M}(\mathcal{X})\) is the dual space of \(C_{0}(\mathcal{X})\). However, to better understand the connection between the Barron space and \(\mathcal{F}_{p,\pi}\) space, it is prefered to take the moment-based definition [1, 1]. Specifically, by extending [1, Proposition 3], we have the following lemma, whose proof can be found in Appendix B.

**Lemma 9** (An alternative definition of Barron spaces).: _For any \(1\leq p\leq\infty\), we have_

\[\mathcal{B}=\cup_{\pi\in\mathcal{P}(\mathcal{V})}\mathcal{F}_{p,\pi},\quad \|f\|_{\mathcal{B}}=\inf_{\pi\in\mathcal{P}(\mathcal{V})}\|f\|_{\mathcal{F}_{p,\pi}}. \tag{16}\]

It is shown that \(\mathcal{B}\) is the union of all \(\mathcal{F}_{p,\pi}\) spaces of a fixed \(p\in[1,\infty]\). Surprisingly, the union is independent of the value of \(p\). One can also treat (16) as an alternative definition of the Barron space \(\mathcal{B}\), which extends the moment-based definition in [1, 1] to general feature maps.

By choosing \(p=2\) and noting \(\mathcal{F}_{2,\pi}=\mathcal{H}_{k_{\pi}}\), we have \(\|f\|_{\mathcal{B}}=\inf_{\pi\in\mathcal{P}(\mathcal{V})}\|f\|_{\mathcal{H}_{ k_{\pi}}}\). This implies that two-layer neural networks can be viewed as _adaptive kernel methods_[1]. Additionally, by setting \(p=1\), we obtain \(\mathcal{B}=\cup_{\pi\in\mathcal{P}(\mathcal{V})}\mathcal{F}_{1,\pi}\), suggesting that \(\mathcal{B}\) is much larger than the \(L^{1}\)-type space \(\mathcal{F}_{1,\pi}\). In particular, if \(\pi\) admits a density on \(\mathcal{V}\), then \(\mathcal{F}_{1,\pi}\) fails to include all the functions implemented by finite-neuron neural networks. All these imply that the Barron space \(\mathcal{B}\) should not be naively interpreted as a \(L^{1}\)-type space and the feature adaptivity plays a more critical role in \(\mathcal{B}\).

**Remark 10**.: _We are aware of that Definition 6 and 8 can be unified by the RKBS framework [1, 11]. However, adopting such an approach would make the definitions, and particularly the statements of our key results in Section 5, overly abstract and difficult to comprehend. Therefore, we will adhere to the concrete definitions presented above and refer interested readers to the concurrent work [1], where the RKBS structures of these spaces are discussed in detail._

## 5 The dual equivalence between approximation and estimation

In this section, we establish a duality framework that connects approximation and estimation for two-layer neural networks and random feature models. To achieve this, we need to define the following conjugate spaces.

**Definition 11** (Conjugate space).: For any \(\gamma\in\mathcal{P}(\mathcal{X})\), let \(\tilde{\mathcal{F}}_{q,\gamma}\) be a function space over the weight space \(\mathcal{V}\) given by

\[\tilde{\mathcal{F}}_{q,\gamma}=\left\{g=\int_{\mathcal{X}}b(x) \phi(x,\cdot)\,\mathrm{d}\,\gamma(x):\,b\in L^{q}(\gamma)\right\}\]

equipped with the norm

\[\|g\|_{\tilde{\mathcal{F}}_{q,\gamma}}=\inf_{b\in L^{q}(\gamma)} \|b\|_{q,\gamma},\quad\text{where}\,B_{f}=\left\{b\in L^{q}(\gamma):\,g=\int_ {\mathcal{X}}b(x)\phi(x,\cdot)\,\mathrm{d}\,\gamma(x)\right\}.\]

Similarly, we define the \(\tilde{\mathcal{B}}\) space on \(\mathcal{V}\):

\[\tilde{\mathcal{B}}=\left\{g=\int_{\mathcal{X}}\phi(x,\cdot)\, \mathrm{d}\,\mu(x):\mu\in\mathcal{M}(\mathcal{X})\right\}\]

and the norm is defined in the same way as (15).

It is worth noting that the function spaces \(\tilde{\mathcal{F}}_{q,\gamma}\) and \(\tilde{\mathcal{B}}\) are defined over the weight domain \(\mathcal{V}\), while \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) are defined over the input domain \(\mathcal{X}\).
### Main result

For clarity, we will begin by presenting our main result for the interpolation regime.

**Theorem 12** (Interpolation regime).: _Let \(x_{1},\cdots,x_{n}\in\mathcal{X}\)._

1. _For_ \(1<p\leq\infty\)_,_ \(1\leq q<\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1,f(x_{i})=0}\|f\|_{q,\rho}=\sup_{\|g\|_{ \tilde{\mathcal{F}}^{\prime},\rho}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g- \sum_{i=1}^{n}c_{i}\phi(x_{i},\cdot)\right\|_{p^{\prime},\pi}.\] (17)
2. _For_ \(1\leq q<\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{E}_{2},\pi}\leq 1,f(x_{i})=0}\|f\|_{\rho}=\sup_{\|g\|_{ \tilde{\mathcal{F}}_{2},\rho}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g- \sum_{i=1}^{n}c_{i}\phi(x_{i},\cdot)\right\|_{C_{0}(\mathcal{V})}\] (18)
3. _For_ \(1<p\leq\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1,f(x_{i})=0}\|f\|_{C_{0}(\mathcal{X})}= \sup_{\|g\|_{\tilde{\mathcal{B}}}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g- \sum_{i=1}^{n}c_{i}\phi(x_{i},\cdot)\right\|_{p^{\prime},\pi}.\] (19)

For each equality stated above, the left-hand side is exactly the \(I\)-complexity that governs the estimation error when learning the corresponding function spaces, as stated in Lemma 3, while the right-hand side is exactly the worse-case error of approximating the corresponding conjugate space with fixed features \(\{\phi(x_{i},\cdot)\}_{i=1}^{n}\). Importantly, these equalities hold for any \(x_{1},\ldots,x_{n}\in\mathcal{X}\), regardless of whether they are sampled from a specific distribution.

Thus, Theorem 12 establishes a form of duality between the estimation and approximation of the \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) spaces. In simpler terms, we can informally summarize the theorem as follows.

* The \(L^{q}(\rho)\) estimation of \(\mathcal{F}_{p,\pi}\) is equivalent to the \(L^{p^{\prime}}(\pi)\) approximation of \(\tilde{\mathcal{F}}_{q^{\prime},\rho}\).
* The \(L^{q}(\rho)\) estimation of \(\mathcal{B}\) is equivalent to the \(L^{\infty}\) approximation of \(\tilde{\mathcal{F}}_{q^{\prime},\rho}\).
* The \(L^{\infty}\) estimation of \(\mathcal{F}_{p,\pi}\) is equivalent to the \(L^{p^{\prime}}(\pi)\) approximation of \(\tilde{\mathcal{B}}\).

Here the \(L^{\infty}\) should be understood as the uniform metric \(\|\cdot\|_{C_{0}(\mathcal{X})}\).

**Remark 13**.: _Regarding Theorem 12, it is worth noting that we conjecture that (17) and (19) do not hold when \(p=1\). This is due to our proof relying on the property \(L^{p}(\pi)=(L^{p^{\prime}}(\pi))^{*}\) for \(1<p<\infty\). Nevertheless, this property does not hold in general for \(p=1\), i.e., \(L^{1}(\pi)\) is not the dual of \(L^{\infty}(\pi)\)._

To better understand the dual equivalence, we examine some concrete cases below.

Case 1.Consider the case of \(q=2\). For \(p=2\), we have

\[\sup_{\|f\|_{\mathcal{F}_{2},\pi}\leq 1,\,f(x_{i})=0}\|f\|_{\rho}=\sup_{\|g\|_{ \tilde{\mathcal{F}}_{2},\rho}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g- \sum_{i=1}^{n}c_{i}\phi(x_{i},\cdot)\right\|_{\pi}, \tag{20}\]
implying that the \(L^{2}\) estimation of a RKHS is equivalent to the \(L^{2}\) approximation of a conjugate RKHS. For the Barron space, we have

\[\sup_{\|f\|_{\mathcal{B}}\leq 1,\,f(x_{i})=0}\|f\|_{\rho}=\sup_{\|g\|_{\tilde{ \mathcal{F}}_{2,\rho}}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g-\sum_{i=1}^{n}c_{i} \phi(x_{i},\cdot)\right\|_{C_{0}(\mathcal{X})}, \tag{21}\]

implying that estimating the Barron space is equvalent to the uniform approximation of an associated RKHS.

By comparing (20) and (21), we can observe that estimatimations of two-layer neural networks and random feature models are equivalent to the approximation of the same RKHS but under different norms to measure approximation errors (\(L^{2}\) vs. \(L^{\infty}\)). This can also be interpreted as a precise characterization of how much larger the space \(\mathcal{B}\) is compared to \(\mathcal{F}_{2,\pi}\).

Case 2.When \(p=2,q=\infty\), we have

\[\sup_{\|f\|_{\mathcal{F}_{2,\pi}}\leq 1,\,f(x_{i})=0}\|f\|_{C_{0}(\mathcal{X}) }=\sup_{\|g\|_{\mathcal{B}}\leq 1}\inf_{c_{1},\cdots,c_{n}}\left\|g-\sum_{i=1}^ {n}c_{i}\phi(x_{i},\cdot)\right\|_{\pi}\]

The left hand side corresponds to the \(I\)-complexity that governs the \(L^{\infty}\) estimation error of learning \(\mathcal{F}_{2,\pi}\). This implies that we can obtain the \(L^{\infty}\) estimation error through the \(L^{2}\) approximation of the corresponding Barron space. By utilizing this approach, we conduct a comprehensive analysis of when the \(L^{\infty}\) estimation of RKHS exhibits CoD or not in Section 7.

Case 3.For \(1<p\leq 2\), \(q=2\), we have

\[\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1}\inf_{c_{1},\cdots,c_{m}}\left\|f- \sum_{j=1}^{m}c_{j}\phi(\cdot,v_{j})\right\|_{\rho}=\sup_{\|g\|_{\tilde{ \mathcal{F}}_{2,\rho}}\leq 1,\,g(x_{i})=0}\|g\|_{p^{\prime},\pi},\]

The left hand side is the worst-case error of approximating \(\mathcal{F}_{p,\pi}\) with random features. When \(1<p<2\), \(\mathcal{F}_{p,\pi}\) is larger than the RKHS \(\mathcal{F}_{2,\pi}\). Therefore, this duality allows to study the random feature approximation beyond RKHS. In Section 6, we delve into this observation in detail.

The non-interpolation regime.We now present the general form of the duality equivalence, which applies to the non-interpolation regime.

**Theorem 14**.: _Let \(\nu\in\mathcal{P}(\mathcal{X})\) be a probability distribution and \(1<r\leq\infty\)._

1. _For_ \(1<p\leq\infty,\,1\leq q<\infty\)_, suppose that_ \(\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1}\|f\|_{r,\nu}<\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1,\|f\|_{r,\nu}\leq\epsilon}\|f\|_{q, \rho}=\sup_{\|g\|_{\tilde{\mathcal{F}}^{\prime},\rho}\leq 1}\inf_{c\in L^{r^{ \prime}}(\nu)}\left(\left\|g-\int_{\mathcal{X}}c(x)\phi(x,\cdot)\,\mathrm{d}\, \nu(x)\right\|_{p^{\prime},\pi}+\epsilon\|c\|_{r^{\prime},\nu}\right).\] (22)
2. _For_ \(1\leq q<\infty\)_, suppose that_ \(\sup_{\|f\|_{\mathcal{B}}\leq 1}\|f\|_{r,\nu}<\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{B}}\leq 1,\|f\|_{r,\nu}\leq\epsilon}\|f\|_{q,\rho}= \sup_{\|g\|_{\mathcal{F}^{\prime},\rho}\leq 1}\inf_{c\in L^{r^{\prime}}(\nu)} \left(\left\|g-\int_{\mathcal{X}}c(x)\phi(x,\cdot)\,\mathrm{d}\,\nu(x)\right\| _{C_{0}(\mathcal{V})}+\epsilon\|c\|_{r^{\prime},\nu}\right).\] (23)
3. _For_ \(1<p\leq\infty\)_, suppose that_ \(\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1}\|f\|_{r,\nu}<\infty\)_, we have_ \[\sup_{\|f\|_{\mathcal{F}_{p},\pi}\leq 1,\|f\|_{r,\nu}\leq\epsilon}\|f\|_{C_{0 }(\mathcal{X})}=\sup_{\|g\|_{\mathcal{B}}\leq 1}\inf_{e\in L^{r^{\prime}}(\nu)} \left(\left\|g-\int_{\mathcal{X}}c(x)\phi(x,\cdot)\,\mathrm{d}\,\nu(x)\right\| _{p^{\prime},\pi}+\epsilon\|c\|_{r^{\prime},\nu}\right).\] (24)

Note that taking \(\nu=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}\) and \(\epsilon=0\) recovers Theorem 12. Comparing with Theorem 12, we introduce another duality pairing: the \(L^{r}(\nu)\) constraint on fitting errors (\(\|f\|_{r,\nu}\leq\epsilon\)) in estimation and the \(L^{r^{\prime}}(\nu)\) regularization of the coefficient function (\(\epsilon\|c\|_{r^{\prime},\nu}\)) in approximation. Specifically, Theorem 14 generalizes Theorem 12 in the following ways:

* First, the right hand side represents the error of approximation with the norm of coefficients regularized. This becomes more intuitive by taking \(\nu=\hat{\rho}_{n}\), in which case the right hand side of (22) becomes \[\sup_{g\in\tilde{\mathcal{F}}_{q^{\prime},\rho}}\inf_{c_{1},\ldots,c_{n}}\left( \|f-\sum_{i=1}^{n}c_{i}\phi(x_{i},\cdot)\|_{p^{\prime},\pi}+\epsilon\left( \frac{1}{n}\sum_{i=1}^{n}|c_{j}|^{p}\right)^{1/p}\right).\] This allows us to study regularized estimators whose coefficient norms can be well controlled. For more details, see Section 6.
* Second, the choice of \(\nu\) is flexible and not limited to the empirical distribution \(\hat{\rho}_{n}\). For instance, by taking \(\nu=\rho\), the left hand side becomes the \(I\)-complexity that provides a lower bound for the distribution-dependent minimax error, as shown in Lemma 4.

We remark that the generality of Theorem 14 allows us to tailor the duality equivalence to different scenarios and provides a more comprehensive understanding of the trade-off between approximation and estimation errors.

### An intuitive proof of Theorem 14

Here we provide a proof for the special case of (22) (the proofs for (23) and (24) are similar) in Theorem 14 to illustrate the role of duality in our analysis. Assuming strong duality, we show that the optimization problems on both sides of (22) are the Lagrangian dual of each other. For a formal proof of Theorem 14, we refer to Appendix C.

Proof.: _(Informal)_ For \(g\in\tilde{\mathcal{F}}_{q^{\prime},\rho}\), let \(e=g-\int_{\mathcal{X}}c(x)\phi(x,\cdot)\,\mathrm{d}\,\nu(x)\). Then, minimization problem in the right hand side of (22) can be written in the following constrained form

\[\inf_{c\in L^{r^{\prime}}(\nu),e\in L^{p^{\prime}}(\pi)} \|e\|_{p^{\prime},\pi}+\epsilon\|c\|_{r^{\prime},\nu}\] \[\text{s.t. }e=g-\int_{\mathcal{X}}c(x)\phi(x,\cdot)\, \mathrm{d}\,\nu(x),\]

The associated Lagrangian: \(J_{g}:L^{r^{\prime}}(\nu)\times L^{p^{\prime}}(\pi)\times L^{p}(\pi)\mapsto \mathbb{R}\) is given by

\[\mathcal{J}_{g}(c,e,\lambda)=\|e\|_{p^{\prime},\pi}+\int_{\mathcal{V}}\lambda (v)\left(g(v)-\int_{\mathcal{X}}c(x)\phi(x,v)\,\mathrm{d}\,\rho(x)-e(v)\right) \mathrm{d}\,\pi(v)+\epsilon\|c\|_{r^{\prime},\nu}.\]
The dual objective \(\mathcal{D}_{g}(\lambda)=\inf_{c,e}J(c,e,\lambda)\) is given by

\[\mathcal{D}_{g}(\lambda)=\begin{cases}\int_{\mathcal{V}}\lambda(v)g(v)\,\mathrm{d }\,\pi(v),&\quad\text{if }\left\|\int_{\mathcal{V}}\lambda(v)\phi(\cdot,v)\,\mathrm{d}\,\pi(v) \right\|_{r,\nu}\leq\epsilon,\,\|\lambda\|_{p,\pi}\leq 1,\\ -\infty,&\quad\text{otherwise,}\end{cases}\]

Hence, the dual problem is

\[\sup_{\lambda\in S}\int_{\mathcal{V}}\lambda(v)g(v)\,\mathrm{d}\,\pi(v),\]

where

\[S=\left\{\lambda\in L^{p}(\pi):\left\|\int_{\mathcal{V}}\lambda(v)\phi(\cdot, v)\,\mathrm{d}\,\pi(v)\right\|_{r,\nu}\leq\epsilon,\,\|\lambda\|_{p,\pi}\leq 1 \right\}. \tag{25}\]

By strong duality we arrive at

\[\inf_{c\in L^{r^{\prime}}(\nu)}\left(\left\|g-\int_{\mathcal{X}}c(x)\phi(x, \cdot)\,\mathrm{d}\,\nu(x)\right\|_{p^{\prime},\pi}+\epsilon\|c\|_{r^{\prime}, \nu}\right)=\sup_{\lambda\in S}\langle\lambda,g\rangle. \tag{26}\]

Now we take supremum over the unit ball of \(\tilde{\mathcal{F}}_{q^{\prime},\rho}\) on the both sides of (26):

\[\sup_{\|g\|_{\tilde{\mathcal{F}}_{q^{\prime},\rho}}\leq 1} \sup_{\lambda\in S}\langle\lambda,g\rangle =\sup_{\|b\|_{q^{\prime},\rho}\leq 1}\sup_{\lambda\in S}\int_{ \mathcal{V}}\lambda(v)\left(\int_{\mathcal{X}}b(x)\phi(x,v)\,\mathrm{d}\,\rho( x)\right)\mathrm{d}\,\pi(v)\] \[=\sup_{\|b\|_{q^{\prime},\rho}\leq 1}\sup_{\lambda\in S}\int_{ \mathcal{X}}b(x)\left(\int_{\mathcal{V}}\lambda(v)\phi(x,v)\,\mathrm{d}\,\pi(v )\right)\mathrm{d}\,\rho(x)\] \[=\sup_{\|b\|_{q^{\prime},\rho}\leq 1}\sup_{\|f\|_{\mathcal{F} _{p,\pi}}\leq 1,\|f\|_{r,\nu}\leq\epsilon}\int_{\mathcal{X}}b(x)f(x)\, \mathrm{d}\,\rho(x)\] \[=\sup_{\|f\|_{\mathcal{F}_{p,\pi}}\leq 1,\|f\|_{r,\nu}\leq \epsilon}\sup_{\|b\|_{q^{\prime},\rho}\leq 1}\int_{\mathcal{X}}b(x)f(x)\, \mathrm{d}\,\rho(x)\] \[=\sup_{\|f\|_{\mathcal{F}_{p,\pi}}\leq 1,\|f\|_{r,\nu}\leq \epsilon}\|f\|_{q,\rho},\]

where the third step follows from the definition of \(S\) in (25). Hence, we complete the proof. 

## 6 Random feature learning beyond kernel regime

In this section, we employ the duality framework to investigate the learnability of functions in \(\mathcal{F}_{p,\pi}\) using RFMs. While prior analyses of RFMs have primarily focused on the case where \(p=2\), our duality framework enables us to examine the entire range of \(p\in(1,\infty)\). The crux of our approach involves employing a (local) Rademacher complexity-based bound in the dual space, where the problem is significantly simplified.

We first introduce the assumptions about the feature function \(\phi\), which is required for our duality analysis. We fist make some boundedness assumption.

**Assumption 15**.: In the case of \(2\leq q<\infty\), we assume that there exists a constant \(M_{q}\) such that \(\|\phi(\cdot,v)\|_{q,\rho}\leq M_{q}\) for any \(v\in\mathcal{V}\). In the case of \(q=\infty\), we assume \(\phi(\cdot,v)\in C_{0}(\mathcal{X})\) and \(\|\phi(\cdot,v)\|_{\infty}\leq M_{\infty}\) for any \(v\in\mathcal{V}\).

We also assume that the Rademacher complexities of the corresponding \(\mathcal{F}_{p,\pi}\) and \(\mathcal{B}\) space are well-controlled.
**Assumption 16**.: We assume a Rademacher complexity bound for the space \(\tilde{\mathcal{F}}_{q^{\prime},\rho}\) or \(\tilde{\mathcal{B}}\) space: there exists a constant \(R_{q}\) such that for any \(v_{1},\cdots,v_{n}\in\mathcal{V}\),

\[\widehat{\operatorname{Rad}}_{n}(\tilde{\mathcal{F}}_{q^{\prime},\rho}(1))\leq\frac{R_{q}}{\sqrt{n}}\quad\text{for the case}\,2\leq q<\infty, \tag{27}\] \[\text{or}\quad\widehat{\operatorname{Rad}}_{n}(\tilde{\mathcal{B} }(1))\leq\frac{R_{\infty}}{\sqrt{n}}\quad\text{for the case}\,q=\infty. \tag{28}\]

Note that \(O(n^{-1/2})\) is the natural scaling of the Rademacher complexity of most function classes of interest. The following lemma demonstrates that the Rademacher complexity bounds specified in Assumption 16 are applicable to many natural choices of feature function \(\phi\). The proof is provided in Appendix D.1.

**Lemma 17**.:
1. _For_ \(2\leq q<\infty\)_, suppose that the activation function_ \(\phi\) _satisfies_ \[\|\phi(\cdot,v)\|_{\rho}\leq R,\] _for any_ \(v\in\mathcal{V}\)_. Then (_27_) in Assumption_ 16 _holds with_ \(R_{q}\leq\sqrt{q}R\)__
2. _For_ \(q=\infty\)_, if_ \(\mathcal{X}\) _and_ \(\mathcal{V}\) _are both supported on_ \(\{x:\|x\|_{2}\leq R\}\) _and_ \(\phi(x,v)=\sigma(x^{\top}v)\)_, where_ \(\sigma:\mathbb{R}\to\mathbb{R}\) _is_ \(L\)_-Lipschitz and_ \(\sigma(0)=0\)_. Then (_28_) in Assumption_ 16 _holds with_ \(R_{\infty}\leq LR^{2}\)_._

Next, we present the random feature approximation bound for functions in \(\mathcal{F}_{p,\pi}\):

**Theorem 18**.: _Suppose \(1<p\leq 2\) and \(v_{j}\stackrel{{\text{iid}}}{{\sim}}\pi\) for \(j\in[m]\). If Assumption 15 and 16 hold, then w.p. at least \(1-\delta\) over the sampling of \(\{v_{j}\}_{j=1}^{m}\), there exists an absolute constant \(C_{1}\), such that for any \(C\geq C_{1}\), we have_

\[\sup_{\|f\|_{\mathcal{F}_{p,\pi}}\leq 1}\inf_{\|\mathbf{c}\|_{p} \leq Cm^{1/p}}\left\|f-\frac{1}{m}\sum_{j=1}^{m}c_{j}\phi(\cdot,v_{j})\right\| _{q,\rho}\lesssim\left(\frac{M_{q}^{p^{\prime}-2}R_{q}^{2}\log^{3}m+M_{q} \log(1/\delta)}{m}\right)^{1/p^{\prime}},\,2\leq q<\infty.\] \[\sup_{\|f\|_{\mathcal{F}_{p,\pi}}\leq 1}\inf_{\|\mathbf{c}\|_{p} \leq Cm^{1/p}}\left\|f-\frac{1}{m}\sum_{j=1}^{m}c_{j}\phi(\cdot,v_{j})\right\| _{C_{0}(\mathcal{X})}\lesssim\left(\frac{M_{\infty}^{p^{\prime}-2}R_{\infty}^ {2}\log^{3}m+M_{\infty}\log(1/\delta)}{m}\right)^{1/p^{\prime}}. \tag{29}\]

The proof is deferred to Appendix D.2. This theorem establishes the uniform approximability of \(\mathcal{F}_{p,\pi}\) for RFMs. In other words, upon sampling the random features \(\phi(\cdot,v_{1}),\ldots,\phi(\cdot,v_{m})\), any function in \(\mathcal{F}_{p,\pi}(1)\) can be approximated effectively using these features. This finding is in agreement with the common use of RFMs in practice, where a single set of random features is repeatedly used to learn multiple functions through optimization of outer coefficients.

Note that the rate of approximation error scales as \(O(m^{-(p-1)/p})\). As \(p\) approaches \(1\), this rate deteriorates, consistent with the observation that \(\mathcal{F}_{p,\pi}\) becomes larger as \(p\) decreases towards \(1\), as shown in (13). It should be noted that our bound blows up when \(p=1\), but this does not imply that \(\mathcal{F}_{1,\pi}\) cannot be approximated by RFMs with a rate. In fact, \(\mathcal{F}_{1,\pi}\) is a subset of \(\mathcal{B}\) and \(\mathcal{B}\) can be approximated with a rate by RFMs. However, in general, the rate scales like \(O(m^{-1/d})\)[22], which suffers from the CoD if no further conditions on the feature function and weight distribution are imposed. These observations suggest that our bound is not tight when \(p\) is close to \(1\).

It is noteworthy that the approximation rate is independent of the value of \(q\) for all cases. Specifically, the \(L^{2}\) approximation and the \(L^{\infty}\) approximation have the same rate. This contrasts with the estimation problem, where \(L^{\infty}\) estimation suffers from the CoD, while \(L^{2}\) estimation does not. More detailed discussion on this issue can be found in Section 7.
Comparison with [16].The special case of \(p=q=2\) (i.e., the \(L^{2}(\pi)\) approximation of the RKHS \(\mathcal{F}_{2,\pi}\)) has been proved in [16]. However, the proof heavily relies on the Hilbert structure of \(\mathcal{F}_{2,\pi}\) and exploits the corresponding covariance operator. In contrast, our result holds for a general choice of \(p\) and \(q\) and is derived naturally from our duality framework. Notably, our proof is substantially simpler and more concise.

Theorem 18 provides bounds solely on the approximation error. We next study the learning under finite sample case.

**Theorem 19**.: _Suppose that \(f^{*}\in\mathcal{F}_{p,\pi}(1)\) and \(x_{i}\overset{\text{iid}}{\sim}\rho\), \(y_{i}=f^{*}(x_{i})+\xi_{i}\), where the noise is distributed as \(\xi_{i}\sim\mathcal{N}(0,\varsigma^{2})\). Let \(v_{1},\cdots,v_{m}\) be i.i.d. random weights sampled from \(\pi\). Consider the estimator \(\hat{f}=\frac{1}{m}\sum_{j=1}^{m}\hat{c}_{j}\phi(\cdot,v_{j})\) with \(\hat{c}\) given by_

\[\hat{c}:=\operatorname*{argmin}_{\|c\|_{p}\leq\lambda}\frac{1}{n}\sum_{i=1}^{ n}\left(y_{i}-\frac{1}{m}\sum_{j=1}^{m}c_{j}\phi(x_{i},v_{j})\right)^{2}. \tag{30}\]

_Assume \(\sup_{x\in\mathcal{X},v\in\mathcal{V}}|\phi(x,v)|\leq M\). Then, with an appropriate choice of \(\lambda\), for any \(\delta\in(0,1)\), it holds w.p. at least \(1-\delta\) over the sampling of data \(\{(x_{i},y_{i})\}_{i=1}^{n}\) and features \(\{v_{j}\}_{j=1}^{m}\) that_

\[\|\hat{f}-f^{*}\|_{\rho}^{2}\lesssim M\varsigma\sqrt{\frac{p^{\prime}+\log(1/ \delta)}{n}}+\frac{p^{\prime}M^{2}\log^{3}n+M\log(1/\delta)}{n}+\left(\frac{M ^{p^{\prime}}\log^{3}m+M\log(1/\delta)}{m}\right)^{2/p^{\prime}}.\]

This theorem provides an upper bound of the total error of learning functions in \(\mathcal{F}_{p,\pi}\) and the proof is deferred to Appendix D.3. Note that here we focus on norm-constrained estimators but similar arguments can be straightforwardly extended to penalized estimators. The upper bound on the total error is comprised of two components: the estimation error and the approximation error. Notably, the estimation error rate is independent of the value of \(p\), and exhibits scaling of \(O(n^{-1})\) in the noiseless case, and \(O(n^{-1/2})\) in the presence of noise. This stands in contrast to the approximation error, for which the error rate deteriorates as decreasing \(p\) to \(1\).

In summary, we have proved that RFMs can effectively learn functions in \(\mathcal{F}_{p,\pi}\) as long as \(p>1\) and is independent of \(d\). This demonstrates the applicability of RFMs beyond the kernel regime where \(p=2\).

## 7 \(L^{\infty}\) learnability of RKHS

It is well-known that functions in RKHS can be learned efficiently under the \(L^{2}\) metric but this may not be sufficient when the \(L^{\infty}\) metric is more relevant, e.g., in security- and safety-critical applications. In this section, we consider the problem of learning functions in RKHS under the \(L^{\infty}\) norm:

\[\|\hat{f}-f^{*}\|_{\infty}=\|\hat{f}-f^{*}\|_{C_{0}(\mathcal{X})},\]

where \(\hat{f}\) is an estimator and \(f^{*}\) is the target function, respectively.

By Lemma 7, for any kernel \(k\), there exist \(\phi:\mathcal{X}\times\mathcal{V}\mapsto\mathbb{R}\) and \(\pi\in\mathcal{P}(\mathcal{V})\) such that \(k(x,x^{\prime})=k_{\pi}(x,x^{\prime})=\int_{\mathcal{V}}\phi(x,v)\phi(x^{ \prime},v)\,\mathrm{d}\pi(v)\) and \(\mathcal{H}_{k}=\mathcal{F}_{2,\pi}\). Hence it suffice to consider the \(\mathcal{F}_{2,\pi}\) space, for which we can apply our dual equivalence. Specifically, Theorem 12 implies that the \(L^{\infty}\) estimation of \(\mathcal{F}_{2,\pi}\) is equivalent to the \(L^{2}(\pi)\)-approximation of \(\tilde{\mathcal{B}}\) with random features; the latter has been systematically investigated in [14, 15]. Specifically, we shall utilize the spectral-based approach developed in [14] in our analysis.
### Lower bounds

To present our results, we need to introduce the dual kernel. For any \(\gamma\in\mathcal{P}(\mathcal{V})\), define the dual kernel \(\tilde{k}_{\gamma}:\mathcal{V}\times\mathcal{V}\to\mathbb{R}\) as

\[\tilde{k}_{\gamma}(v,v^{\prime}):=\int_{\mathcal{X}}\phi(x,v)\phi(x,v^{\prime}) \,\mathrm{d}\,\gamma(x). \tag{31}\]

**Theorem 20**.: _Recall that \(\Lambda_{\tilde{k}_{\gamma},\pi}(m)=\sqrt{\sum_{i=m+1}^{\infty}\mu_{i}^{ \tilde{k}_{\gamma},\pi}}\), where \(\{\mu_{i}^{\tilde{k}_{\gamma},\pi}\}_{i=1}^{\infty}\) denotes the spectrum of the dual kernel \(\tilde{k}_{\gamma}\) with respect to \(\pi\) in a decreasing order. Let \(\tilde{\Lambda}_{\pi}(m)=\sup_{\gamma\in\mathcal{P}(\mathcal{V})}\Lambda_{ \tilde{k}_{\gamma},\pi}(m)\). Recall that we use \(\mathcal{A}_{n}\) to denote the set of all measurable estimators._

1. _For any input data_ \(x_{1},\cdots,x_{n}\in\mathcal{X}\)_. We have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{F}_{2,\pi} }\leq 1}\|T_{n}(\{(x_{i},f(x_{i}))\}_{i=1}^{n})-f\|_{C_{0}(\mathcal{X})}\gtrsim \tilde{\Lambda}_{\pi}(m).\]
2. _Suppose that_ \(x_{i}\stackrel{{ iid}}{{\sim}}\rho,\xi_{i}\stackrel{{ iid}}{{\sim}}\mathcal{N}(0,\varsigma^{2})\)_. Let_ \(\tilde{s}_{\rho}=\int_{\mathcal{V}}\tilde{k}_{\rho}(v,v)\,\mathrm{d}\,\pi(v)\) _be the trace of_ \(\tilde{k}_{\rho}\)_, we have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{F}_{2,\pi} }\leq 1}\mathbb{E}\,\|T_{n}(\{(x_{i},f(x_{i})+\xi_{i})\}_{i=1}^{n})-f\|_{C_{ 0}(\mathcal{X})}\gtrsim\min\left(1,\frac{\varsigma}{\sqrt{\tilde{s}_{\rho}}} \right)\tilde{\Lambda}_{\pi}(m).\]

The proof is deferred to Appendix E.1. This theorem shows that the error of \(L^{\infty}\) estimation can be lower bounded using the spectrum of dual kernels in both the sample-dependent case and the distribution-dependent case. Next, we further show that lower bounds can also be controlled by the primal kernel \(k\).

**Corollary 21**.: _Let \(\mathcal{H}_{k}\subset C_{0}(\mathcal{X})\) be the RKHS associated with the kernel \(k\)._

1. _For any input data_ \(x_{1},\cdots,x_{n}\in\mathcal{X}\)_, we have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{H}_{k}}\leq 1}\|T_{n}(\{(x_{i},f(x_{i}))\}_{i=1}^{n})-f\|_{C_{0}(\mathcal{X})}\gtrsim\sup_{\gamma\in \mathcal{P}(\mathcal{X})}\Lambda_{k,\gamma}(m).\]
2. _Suppose that_ \(x_{i}\stackrel{{ iid}}{{\sim}}\rho,\xi_{i}\stackrel{{ iid}}{{\sim}}\mathcal{N}(0,\varsigma^{2})\)_. Let_ \(s_{\rho}=\int_{\mathcal{X}}k(x,x)\,\mathrm{d}\,\rho(x)\) _be the trace of_ \(k\)_. We have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{H}_{k}}\leq 1}\mathbb{E}\,\|T_{ n}(\{(x_{i},f(x_{i})+\xi_{i})\}_{i=1}^{n})-f\|_{C_{0}(\mathcal{X})}\gtrsim \min\left(1,\frac{\varsigma}{\sqrt{s_{\rho}}}\right)\sup_{\gamma\in\mathcal{ P}(\mathcal{X})}\Lambda_{k,\gamma}(m).\]

The above result relies on the \(\mathcal{F}_{2,\pi}\) representation of the RKHS, which is established in Lemma 7. Specifically, we show that for any kernel \(k\), there exist a feature function \(\phi:\mathcal{X}\times\mathcal{V}\mapsto\mathbb{R}\) and a probability measure \(\pi\in\mathcal{P}(\mathcal{V})\) such that \(\mathcal{H}_{k}=\mathcal{F}_{2,\pi}\) and the spectrum of the corresponding dual kernel is the same as that of \(k\). This provides a crucial link between the primal and dual representations of the RKHS, and enables us to leverage the duality framework to derive the minimax estimation rate. For a detailed proof, we refer to Appendix E.2.
### Upper bounds

We now turn to establish similar upper bounds of uniform estimation errors. Specifically, we focus on the dot-product kernels. Assume \(\mathcal{X}=\mathcal{V}=\mathbb{S}^{d-1},\pi=\rho=\tau_{d-1}\), and the feature function is given by a single neuron without bias: \(\phi(x,v)=\sigma(x^{\top}v)\), where \(\sigma:\mathbb{R}\to\mathbb{R}\) is a nonlinear activation function. In such a case, \(\mathcal{F}_{2,\pi}\) and \(\tilde{\mathcal{F}}_{2,\rho}\) are essentially the same space and we will use \(\mathcal{F}_{2,\tau_{d-1}}\) to denote them without specifying the input domain for simplicity.

The kernel associated to \(\mathcal{F}_{2,\tau_{d-1}}\) is dot-product:

\[k(x,x^{\prime})=\int_{\mathbb{S}^{d-1}}\sigma(v^{\top}x)\sigma(v^{\top}x^{ \prime})\,\mathrm{d}\,\tau_{d-1}(v)=\kappa(x^{\top}x^{\prime}), \tag{32}\]

where \(\kappa:[-1,1]\to\mathbb{R}\). Let \(\{\lambda_{j}\}_{j=1}^{\infty}\) be the eigenvalues of \(k\) on \(L^{2}(\tau^{d-1})\) in a decreasing order. The spectral decomposition of \(k\) is given by

\[\kappa\left(x^{T}x^{\prime}\right)=\sum_{k=0}^{\infty}\sum_{j=1}^{N(d,k)}t_{k }Y_{k,j}(x)Y_{k,j}\left(x^{\prime}\right), \tag{33}\]

where \(t_{k}\) is the eigenvalue and the spherical harmonics \(Y_{k,j}\) is the corresponding eigenfunction that satisfies \(\mathbb{E}_{x^{\prime}\sim\tau_{d-1}}\left[\kappa\left(x^{T}x^{\prime}\right) Y_{k,j}\left(x^{\prime}\right)\right]=t_{k}Y_{j,k}(x)\). Note that \(\{\lambda_{j}\}_{j}\) are the eigenvalues counted with multiplicity, while \(\{t_{k}\}_{k}\) are the eigenvalues counted without multiplicity. We refer to [22, Section 2.1] for more details about the eigendecomposition of dot-product kernels.

**Theorem 22**.: _Suppose \(k:\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}\mapsto\mathbb{R}\) is a dot-product kernel taking the form of (32). For any non-increasing function \(L:\mathbb{N}^{+}\to\mathbb{R}^{+}\) that satisfies \(\Lambda_{k,\tau_{d-1}}(m)\leq L(m)\), let \(q_{L}(d)=\sup_{k\geq 1}\frac{L(k)}{L((d+1)k)}\). Let \(\{(x_{i},y_{i})\}_{i=1}^{n}\) be \(n\) samples indepdently drawn from \(x_{i}\sim\tau_{d-1}\), \(y_{i}=f^{*}(x_{i})+\xi_{i}\), where the noise \(\xi_{i}\)'s are mean-zero and \(\varsigma\)-subgaussian and the target function \(f^{*}\in\mathcal{H}_{k}(1)\). Consider the estimator_

\[\hat{f}=\operatorname*{argmin}_{\|f\|_{\mathcal{H}_{k}}\leq 1}\frac{1}{n}\sum_{ i=1}^{n}(f(x_{i})-y_{i})^{2}.\]

_Then with probability at least \(1-\delta\) over the sampling of \(\{(x_{i},y_{i})\}_{i=1}^{n}\), we have_

\[\|\hat{f}-f^{*}\|_{C_{0}(\mathbb{S}^{d-1})}\lesssim\inf_{m\geq 1}\left[ \sqrt{q_{L}(d)L(m)}+\sqrt{m}(\epsilon(n,\varsigma,\delta)+e(n,\delta)) \right], \tag{34}\]

_where \(\epsilon(n,\varsigma,\delta)=\left(\frac{\varsigma^{2}\kappa(1)(1+\log(1/ \delta))}{n}\right)^{1/4},\)\(e(n,\delta)=\sqrt{\frac{\kappa(1)^{2}\log^{3}n+\kappa(1)\log(1/\delta)}{n}}\)._

This theorem presents a spectral-based upper bound for the \(L^{\infty}\) estimation error and the proof can be found in Appendix E.3. To obtain the tightest bound, one can choose \(L(m)=\Lambda_{k,\tau_{d-1}}(m)\). However, since the exact value of \(\Lambda_{k,\tau_{d-1}}(m)\) is often unknown, the introduction of \(L(m)\) is mainly for the convenience of calculating the constant \(q_{L}(d)\).

Take \(L(m)=\Lambda_{k,\tau_{d-1}}(m)=\sum_{j=m+1}^{\infty}\lambda_{j}\). If \(\lambda_{j}\sim j^{-(1+2\beta)}\), then we roughly have that \(L(m)\sim m^{-2\beta}\) and \(q_{L}(d)\sim d^{2\beta}\). Plugging them into (34) yields

\[\|\hat{f}-f^{*}\|_{C_{0}(\mathcal{X})}\lesssim_{\beta,\varsigma,\delta}\inf_{m \geq 1}\left(d^{\beta}m^{-\beta}+m^{1/2}n^{-1/4}\right)\lesssim_{\beta,\varsigma, \delta}d^{\frac{\beta}{2\beta+1}}n^{-\frac{\beta}{2(2\beta+1)}}, \tag{35}\]

where we hide constants that depend on \(\beta,\varsigma\) and \(\delta\). It is evident that if \(\beta\) does not depend on \(d\), then the error rate does not exhibit the CoD.
**Remark 23**.: _The rotational invariance assumption plays a critical role in the analysis presented above, and the result may potentially be extended to settings where the densities of \(\pi\) and \(\rho\) are strictly positive. In addition, by utilizing localization techniques (see, e.g., [20, Chapter 13]) to tackle noise-induced errors, one may be able to obtain tighter bounds. However, our main focus here is to understand how the error rate depends on the kernel spectrum, rather than to pursue optimal rates._

### Examples

We now turn to instantiate the lower and upper bounds established above for concrete examples. Specifically, we focus on dot-product kernels that take the form of (32) and discuss how the smoothness of \(\sigma(\cdot)\) affects the \(L^{\infty}\) learnability. These kernels are of particular interest in understanding RFMs and neural networks [14, 15, 16]. To present our results, we will restate some results from [15, Section 4] when needed.

Non-smooth activations.Consider the ReLU\({}^{\alpha}\) activation function \(\sigma(t)=\max(0,t)^{\alpha}\) with \(\alpha\in\mathbb{N}^{+}\). [15, Proposition 5] shows that there exists a constant \(C_{\alpha,d}\) depending on \(1/d\) polynomially such that

\[\Lambda_{k,\tau_{d-1}}(m)\geq C_{\alpha,d}m^{-\frac{2\alpha+1}{d-1}}. \tag{36}\]

Combining (36) with Corollary 21 yields the follow:

**Corollary 24**.: _For \(\sigma(t)=\max(0,t)^{\alpha}\) with \(\alpha\in\mathbb{N}^{+}\), there exists a constant \(C_{\alpha,d}\) that depends on \(1/d\) polynomially such that_

1. _For any input data_ \(x_{1},\cdots,x_{n}\in\mathcal{X}\)_, we have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{H}_{k}}\leq 1}\|T_{n}(\{(x_{i },f(x_{i}))\}_{i=1}^{n})-f\|_{C_{0}(\mathbb{S}^{d-1})}\geq C_{\alpha,d}n^{- \frac{2\alpha+1}{2(d-1)}}.\]
2. _Suppose_ \(x_{i}\stackrel{{ iid}}{{\sim}}\rho\) _and_ \(\xi_{i}\stackrel{{ iid}}{{\sim}}\mathcal{N}(0,\varsigma^{2})\) _for_ \(i=1,\ldots,n\)_. We have_ \[\inf_{T_{n}\in\mathcal{A}_{n}}\sup_{\|f\|_{\mathcal{H}_{k}}\leq 1}\mathbb{E}\left\|T_ {n}(\{(x_{i},f(x_{i})+\xi_{i})\}_{i=1}^{n})-f\right\|_{C_{0}(\mathbb{S}^{d-1} )}\geq\min(1,\varsigma)C_{\alpha,d}n^{-\frac{2\alpha+1}{2(d-1)}}.\]

The lower bound given in Corollary 24 suggests that kernel methods induced by the ReLU\({}^{\alpha}\) activation functions suffers from CoD. This immediately implies that \(L^{\infty}\) learning with popular ReLU neural networks also suffers from CoD since the Barron space \(\mathcal{B}\) contains the RKHS \(\mathcal{F}_{2,\tau_{d-1}}\) as its subset (according to Lemma 7).

Smooth activations.We now turn to smooth activation functions, such as sigmoid, softplus, arctan, GELU, and Swish/SiLU. All popular smooth activation functions satisfy the following assumption:

**Assumption 25**.: Assume that \(B_{k}:=\max_{t\in\mathbb{R}}|\sigma^{(k)}(t)|\lesssim\Gamma(k-1)\).

See [15] for the verification of this assumption. Under this assumption, [15, Proposition 9] shows that

\[\Lambda_{k,\tau_{d-1}}(m)\lesssim\frac{1}{m}. \tag{37}\]

By asserting \(L(m)=\frac{C}{m}\) in Theorem 22 yields the follow:
**Corollary 26**.: _Suppose \(k:\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}\mapsto\mathbb{R}\) is a dot-product kernel taking the form of (32) and the activation function \(\sigma\) satisfies Assumption 25. Let \(\{(x_{i},y_{i})\}_{i=1}^{n}\) be \(n\) samples indepdently drawn from \(x_{i}\sim\tau_{d-1},\,y_{i}=f^{*}(x_{i})+\xi_{i}\), where the noise \(\xi_{i}\)'s are mean-zero and \(\varsigma\)-subgaussian and the target function \(f^{*}\in\mathcal{H}_{k}(1)\). Consider the estimator_

\[\hat{f}=\operatorname*{argmin}_{\|f\|_{\mathcal{H}_{k}}\leq 1}\frac{1}{n}\sum_{ i=1}^{n}(f(x_{i})-y_{i})^{2}.\]

_Then with probability at least \(1-\delta\) over the sampling of \(\{(x_{i},y_{i})\}_{i=1}^{n}\), we have_

\[\|\hat{f}-f^{*}\|_{C_{0}(\mathbb{S}^{d-1})}\lesssim_{\varsigma,\delta}d^{1/4} n^{-1/8}. \tag{38}\]

Corollary 26 gives that the \(L^{\infty}\) error scales as \(O(n^{-1/8})\). Thus, we can conclude that in this case, the \(L^{\infty}\) learning is tractable.

## 8 Conclusion

In this paper, we proposed a duality framework to analyze the approximation and estimation of the \(\mathcal{F}_{p,\pi}\) and Barron spaces, which is relevant to understand kernel methods, RFMs, and neural networks. Specifically, we establish a dual equivalence between approximation and estimation for learning functions in these spaces, which allows us to convert an approximation problem to an estimation problem and vice versa. Therefore, in analysis, one only needs to focus on the easier one. To demonstrate the power of our duality framework, we provide comprehensive analyses of two specific problems: random feature learning beyond RKHS and the \(L^{\infty}\) estimation of RKHS. Our duality analysis recovers existing results with much simpler proofs and stronger conclusions. To establish the dual equivalence, we introduce an information-based complexity to measure the capacity of a function class and show how it controls the minimax error of estimating that function class.

For future work, it is promising to apply our duality framework to different learning settings, e.g., unsupervised learning, out-of-distribution learning, and reinforcement learning. In this paper, we only consider the supervised learning setting. In fact, a similar analysis has been conducted in [1, 23] to understand reinforcement learning. In addition, the proposed information-based complexity can be also useful for studying the statistical properties of other function spaces. For instance, [17] already adopted similar ideas to study the optimal approximation of various traditional function spaces, such as Sobolev space.

## Acknowledgements

Lei Wu is supported in part by a startup fund from Peking University. Hongrui Chen is partially supported by the elite undergraduate training program of School of Mathematical Sciences at Peking University
