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

Optimal transport (OT) is a popular measure to compare probability
distributions. However, OT suffers a few drawbacks such as (i) a high
complexity for computation, (ii) indefiniteness which limits its applicability
to kernel machines. In this work, we consider probability measures supported on
a graph metric space and propose a novel Sobolev transport metric. We show that
the Sobolev transport metric yields a closed-form formula for fast computation
and it is negative definite. We show that the space of probability measures
endowed with this transport distance is isometric to a bounded convex set in a
Euclidean space with a weighted $\ell_p$ distance. We further exploit the
negative definiteness of the Sobolev transport to design positive-definite
kernels, and evaluate their performances against other baselines in document
classification with word embeddings and in topological data analysis.

本文提出了一种基于图测度空间的概率测度支持的 Sobolev transport metric， 该度量具有计算速度快和负定性等优点，并且可以用于构建正定核，在文本分类和拓扑数据分析中表现良好。

Sobolev 输运：一种基于图度量的可扩展概率度量

Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics

We investigate a recently proposed family of positive-definite kernels that
mimic the computation in large neural networks. We examine the properties of
these kernels using tools from differential geometry; specifically, we analyze
the geometry of surfaces in Hilbert space that are induced by these kernels.
When this geometry is described by a Riemannian manifold, we derive results for
the metric, curvature, and volume element. Interestingly, though, we find that
the simplest kernel in this family does not admit such an interpretation. We
explore two variations of these kernels that mimic computation in neural
networks with different activation functions. We experiment with these new
kernels on several data sets and highlight their general trends in performance
for classification.

本文研究了一种最近提出的伪造大型神经网络计算的正定核族。作者采用微分几何工具来研究这些核的性质，具体地，分析了这些核引起的希尔伯特空间表面的几何特征。当该几何被描述为一个黎曼流形时，作者针对其度量、曲率和体积元素导出了结论。值得注意的是，他们发现这个族中最简单的核不允许这样的解释，因此研究了两个用于类神经网络计算的修改的核。作者在多个数据集上实验了这些新的核，并强调了它们在分类中的普遍趋势。