Fast Sketching of Polynomial Kernels of Polynomial Degree
Fast Sketching of Polynomial Kernels of Polynomial Degree
复制标题
DOI：
--
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Zhao Song;David P. Woodruff;Zheng Yu;Lichen Zhang
中科院分区：
文献类型：
--
作者：
Zhao Song;David P. Woodruff;Zheng Yu;Lichen Zhang
核方法是机器学习的基础，更快的核近似算法为机器学习中的许多核心任务提供了直接加速。多项式核尤其重要，因为其他核通常可以通过泰勒级数展开由多项式核来近似。最近的不经意草图技术减少了运行时间对多项式内核从指数到多项式的次数 $q$ 的依赖性，这对于高斯内核很有用，因为可以选择 $q$ 为多对数。然而，对于增长较慢的内核，例如神经正切和反余弦内核，$q$ 需要是多项式，而之前的工作会导致运行时间因多项式因子而减慢。我们给出了一个新的不经意的草图，通过消除对前导项中 $q$ 的依赖，极大地改善了运行时间。结合新颖的采样方案，我们提供了最快的算法来近似一大群缓慢增长的内核。
Kernel methods are fundamental in machine learning, and faster algorithms for kernel approximation provide direct speedups for many core tasks in machine learning. The polynomial kernel is especially important as other kernels can often be approximated by the polynomial kernel via a Taylor series expansion. Recent techniques in oblivious sketching reduce the dependence in the running time on the degree $q$ of the polynomial kernel from exponential to polynomial, which is useful for the Gaussian kernel, for which $q$ can be chosen to be polylogarithmic. However, for more slowly growing kernels, such as the neural tangent and arc-cosine kernels, $q$ needs to be polynomial, and previous work incurs a polynomial factor slowdown in the running time. We give a new oblivious sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term. Combined with a novel sampling scheme, we give the fastest algorithms for approximating a large family of slow-growing kernels.