In this paper, we conduct a comprehensive analysis of generalization
properties of Kernel Ridge Regression (KRR) in the noiseless regime, a scenario
crucial to scientific computing, where data are often generated via computer
simulations. We prove that KRR can attain the minimax optimal rate, which
depends on both the eigenvalue decay of the associated kernel and the relative
smoothness of target functions. Particularly, when the eigenvalue decays
exponentially fast, KRR achieves the spectral accuracy, i.e., a convergence
rate faster than any polynomial. Moreover, the numerical experiments well
corroborate our theoretical findings. Our proof leverages a novel extension of
the duality framework introduced by Chen et al. (2023), which could be useful
in analyzing kernel-based methods beyond the scope of this work.

我们对核岭回归的泛化性质在无噪声情况下进行了综合分析，证明了核岭回归能够达到最小最优速率，该速率取决于相关核函数的特征值衰减和目标函数的相对平滑度。

噪声无关情况下核岭回归的对偶分析

A Duality Analysis of Kernel Ridge Regression in the Noiseless Regime

Positive definite kernels and their associated Reproducing Kernel Hilbert
Spaces provide a mathematically compelling and practically competitive
framework for learning from data.
In this paper we take the approximation theory point of view to explore
various aspects of smooth kernels related to their inferential properties. We
analyze eigenvalue decay of kernels operators and matrices, properties of
eigenfunctions/eigenvectors and "Fourier" coefficients of functions in the
kernel space restricted to a discrete set of data points. We also investigate
the fitting capacity of kernels, giving explicit bounds on the fat shattering
dimension of the balls in Reproducing Kernel Hilbert spaces. Interestingly, the
same properties that make kernels very effective approximators for functions in
their "native" kernel space, also limit their capacity to represent arbitrary
functions. We discuss various implications, including those for gradient
descent type methods.
It is important to note that most of our bounds are measure independent.
Moreover, at least in moderate dimension, the bounds for eigenvalues are much
tighter than the bounds which can be obtained from the usual matrix
concentration results. For example, we see that the eigenvalues of kernel
matrices show nearly exponential decay with constants depending only on the
kernel and the domain. We call this "approximation beats concentration"
phenomenon as even when the data are sampled from a probability distribution,
some of their aspects are better understood in terms of approximation theory.

探讨了正定核及其相关重现核希尔伯特空间的逼近性质，包括核算子和矩阵的特征值衰减、特征函数 / 特征向量的性质、核空间中函数的 “傅里叶” 系数以及核的拟合能力等，并给出了限制在离散数据点上的重现核希尔伯特空间球体的胖打散维度的明确界限，讨论了正定核的容量限制及其对梯度下降等算法的影响。

近似比集中更有效？平滑径向核推理的近似观点

Approximation beats concentration? An approximation view on inference  with smooth radial kernels

We consider the problem of learning function classes computed by neural
networks with various activations (e.g. ReLU or Sigmoid), a task believed to be
computationally intractable in the worst-case. A major open problem is to
understand the minimal assumptions under which these classes admit provably
efficient algorithms. In this work we show that a natural distributional
assumption corresponding to {\em eigenvalue decay} of the Gram matrix yields
polynomial-time algorithms in the non-realizable setting for expressive classes
of networks (e.g. feed-forward networks of ReLUs). We make no assumptions on
the structure of the network or the labels. Given sufficiently-strong
polynomial eigenvalue decay, we obtain {\em fully}-polynomial time algorithms
in {\em all} the relevant parameters with respect to square-loss. Milder decay
assumptions also lead to improved algorithms. This is the first purely
distributional assumption that leads to polynomial-time algorithms for networks
of ReLUs, even with one hidden layer. Further, unlike prior distributional
assumptions (e.g., the marginal distribution is Gaussian), eigenvalue decay has
been observed in practice on common data sets.

研究神经网络学习使用不同激活函数的函数类的问题，探讨了最小的假设条件，该假设条件相应于 Gram 矩阵的特征值衰减。通过足够强的多项式特征值衰减，他们获得了所有相关参数的多项式时间算法，这是对 ReLU 网络的第一个以纯分布假设为基础的支持多项式时间算法的假设。特征值衰减是实际数据集上的观察结果。