Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Bernstein-Schur 核：通过草图调制与径向随机化实现的随机特征
Abstract: Bernstein—Schur kernels are products of a finite-feature kernel (one with an explicit finite-dimensional feature map) and a completely monotone shift-invariant kernel: nonstationary kernels that fall between the shift-invariant and dot-product templates random features usually exploit, so in general neither Bochner sampling nor polynomial sketching applies to the full kernel directly.
摘要： Bernstein-Schur 核是有限特征核（具有显式有限维特征映射的核）与完全单调平移不变核的乘积：这类非平稳核介于随机特征通常利用的平移不变模板和点积模板之间，因此通常情况下，Bochner 采样和多项式草图（polynomial sketching）都无法直接应用于完整的核。
We give one random-feature construction for the whole class that randomizes both factors: it sketches the finite modulation and randomizes the completely monotone radial factor, sampling the latter’s one-dimensional Bernstein—Widder scale and then applying Gaussian random Fourier features (whose frequency is still $d$-dimensional).
我们为整个类别提供了一种随机特征构造方法，该方法对两个因子同时进行随机化：它对有限调制进行草图化（sketching），并对完全单调的径向因子进行随机化，采样后者的 Bernstein-Widder 一维尺度，然后应用高斯随机傅里叶特征（其频率仍为 $d$ 维）。
The feature dimension is then $Dm$, set by the sketch size $m$ and the radial-draw count $D$, free of the $O(d^2)$ size of the exact modulation feature. Keeping the modulation exact is the analyzable limit ($m\to\infty$): there we prove unbiasedness, an exact variance for the recommended flat estimator, an expected matrix-Bernstein operator-norm bound (with a matching high-probability tail) controlled by the top eigenvalues of the kernel and modulation Gram matrices together with an intrinsic dimension rather than the crude $N\max_{ij}$ entrywise route, and a deterministic relative-spectral kernel-ridge stability result.
特征维度为 $Dm$，由草图大小 $m$ 和径向抽取次数 $D$ 决定，摆脱了精确调制特征 $O(d^2)$ 大小的限制。保持调制精确是可分析的极限情况（$m\to\infty$）：在此极限下，我们证明了无偏性、推荐平坦估计量的精确方差、由核矩阵和调制 Gram 矩阵的最大特征值以及内在维度（而非粗糙的 $N\max_{ij}$ 逐项路径）控制的期望矩阵-Bernstein 算子范数界（具有匹配的高概率尾部），以及确定性的相对谱核岭稳定性结果。
By conditioning on the sketch, the doubly-randomized estimator inherits the same intrinsic-dimension operator-norm guarantee plus a single additive sketch term, tunable by $m$ independently of $D$.
通过对草图进行条件化，双重随机化估计量继承了相同的内在维度算子范数保证，并增加了一个可由 $m$ 独立于 $D$ 进行调节的附加草图项。
The motivating instance is the biased $yat$-kernel $k_{yat,b}(w,x)=(w^\top x+b)^2/(|w-x|^2+\varepsilon)$, $b\ge0$, whose family span contains the inverse-multiquadric kernel by finite differences in $b$; for it the radial mixture is the IMQ spectral sampler, and one frequency per scale is variance-optimal at a fixed radial-feature budget.
该研究的动机实例是有偏 $yat$-核 $k_{yat,b}(w,x)=(w^\top x+b)^2/(|w-x|^2+\varepsilon)$（其中 $b\ge0$），其族跨度通过 $b$ 的有限差分包含了逆多二次（IMQ）核；对于该核，径向混合是 IMQ 谱采样器，且在固定的径向特征预算下，每个尺度一个频率是方差最优的。