Random features are an important technique that make it possible to rewrite
positive-definite kernels as infinite-dimensional dot products. Over time,
increasingly elaborate random feature representations have been developed in
pursuit of finite approximations with ever lower error. We resolve this arms
race by deriving an optimal sampling policy, and show that under this policy
all random features representations have the same approximation error. This
establishes a lower bound that holds across all random feature representations,
and shows that we are free to choose whatever representation we please,
provided we sample optimally.

根据我们导出的最优取样策略，我们证明了在这一策略下，所有的随机特征表示具有相同的逼近误差，从而建立了一个适用于所有随机特征表示的下界，这意味着我们可以根据需求自由选择任何表示方式。

所有随机特征表示等效

All Random Features Representations are Equivalent

Adaptive importance sampling (AIS) uses past samples to update the
\textit{sampling policy} $q_t$ at each stage $t$. Each stage $t$ is formed with
two steps : (i) to explore the space with $n_t$ points according to $q_t$ and
(ii) to exploit the current amount of information to update the sampling
policy. The very fundamental question raised in this paper concerns the
behavior of empirical sums based on AIS. Without making any assumption on the
allocation policy $n_t$, the theory developed involves no restriction on the
split of computational resources between the explore (i) and the exploit (ii)
step. It is shown that AIS is asymptotically optimal : the asymptotic behavior
of AIS is the same as some "oracle" strategy that knows the targeted sampling
policy from the beginning. From a practical perspective, weighted AIS is
introduced, a new method that allows to forget poor samples from early stages.

本文提出了自适应重要性采样方法，并探讨了采样策略和权重更新对采样效率产生的影响。除此之外，还介绍了一种新的加权采样方法，可以帮助快速排除低效样本。