Nonlinear kernels can be approximated using finite-dimensional feature maps
for efficient risk minimization. Due to the inherent trade-off between the
dimension of the (mapped) feature space and the approximation accuracy, the key
problem is to identify promising (explicit) features leading to a satisfactory
out-of-sample performance. In this work, we tackle this problem by efficiently
choosing such features from multiple kernels in a greedy fashion. Our method
sequentially selects these explicit features from a set of candidate features
using a correlation metric. We establish an out-of-sample error bound capturing
the trade-off between the error in terms of explicit features (approximation
error) and the error due to spectral properties of the best model in the
Hilbert space associated to the combined kernel (spectral error). The result
verifies that when the (best) underlying data model is sparse enough, i.e., the
spectral error is negligible, one can control the test error with a small
number of explicit features, that can scale poly-logarithmically with data. Our
empirical results show that given a fixed number of explicit features, the
method can achieve a lower test error with a smaller time cost, compared to the
state-of-the-art in data-dependent random features.

本篇研究针对非线性内核的风险最小化问题，采用有限维特征映射方法来解决映射空间维数与逼近精度之间的折中关系，并提出了一种基于相关性度量的贪心特征选择方法，其结果可以通过一个样本外误差界来描述，从而更好地平衡了逼近误差和谱误差之间的关系，并且当最优模型的谱误差足够小时，只需要较小数量的显式特征即可控制测试误差。