We apply the discrepancy method and a chaining approach to give improved
bounds on the coreset complexity of a wide class of kernel functions. Our
results give randomized polynomial time algorithms to produce coresets of size
$O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$
for the Gaussian and Laplacian kernels in the case that the data set is
uniformly bounded, an improvement that was not possible with previous
techniques. We also obtain coresets of size
$O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the
Laplacian kernel for $d$ constant. Finally, we give the best known bounds of
$O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ on the
coreset complexity of the exponential, Hellinger, and JS Kernels, where
$1/\alpha$ is the bandwidth parameter of the kernel.

应用偏差方法和串联方法提供改进的核函数广泛类别 Coreset 复杂性的界限，并给出对于高斯核和拉普拉斯核，在数据集均匀有界的情况下，产生 O (√d/ε√loglog (1/ε)) 大小的 Coreset 的随机多项式时间算法，这是以前的技术所不可能的改进。此外，对于恒定的 d，我们得到 O (1/ε√loglog (1/ε)) 大小的拉普拉斯核的 Coreset。最后，我们给出了指数核、Hellinger 核和 JS 核 Coreset 复杂性的最佳已知界限，其中 1/α 是核的带宽参数。