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.

本研究通过对学习 Fp,π 和 Barron 空间中的函数这一问题的探讨，揭示了这些空间的逼近和估计可以在某种意义上等价。这使我们能够将重点放在逼近和估计这一较容易的问题上，当研究两个模型的泛化时。此外，我们通过两个具体的应用程序全面分析了我们的二元性框架的灵活性。