Bernstein-Schur 核：基于草图调制和径向随机化的随机特征

###### 摘要  
*Bernstein–Schur核*是有限特征核（具有显式有限维特征映射的核）与完全单调平移不变核的乘积：这类非平稳核介于随机特征通常利用的平移不变型和点积型模板之间，因此一般无法直接对完整核应用Bochner采样或多项式草图。我们为整个核类给出了一种随机特征构造，它对*两个因子均进行随机化*：对有限调制进行草图采样，并对完全单调径向因子进行随机化——先采样其一维Bernstein–Widder尺度，再应用高斯随机傅里叶特征（其频率仍是\(d\)维）。特征维度为\(Dm\)，由草图大小\(m\)和径向抽取次数\(D\)决定，与精确调制特征的\(O(d^2)\)规模无关。保持调制*精确*是可分析极限（\(m\to\infty\)）：在此极限下，我们证明了推荐平坦估计量的无偏性、精确方差、一个由核和调制Gram矩阵的顶部特征值以及内在维度（而非粗略的\(N\max_{ij}\)逐项路径）控制的期望矩阵Bernstein算子范数界（附带匹配的高概率尾界），以及一个确定性的相对谱核岭稳定性结果。通过对草图取条件，双重随机化估计量继承了*相同*的内在维度算子范数保证，外加一个可由\(m\)独立于\(D\)调节的附加草图项。  
动机实例是有偏\(\tifinaghfont{ⵟ}\)核：  
\[
k_{\text{\tifinaghfont ⵟ},b}(w,x)=\frac{(w^\top x+b)^2}{\|w-x\|^2+\varepsilon},\quad b\ge 0,
\]
其函数族通过对\(b\)取有限差分包含反多二次核；对于该核，径向混合是IMQ谱采样器，在固定的径向特征预算下，每个尺度单频率在方差上最优。一个调制–径向误差分解表明，当调制被草图化时，乘积仍然有用：径向噪声被对齐因子调制，而调制误差则被接近性定位。实验在球外验证了该构造——此时核真正非点积型，均匀和k-means Nyström在匹配地标数量时随\(d\)退化（而在匹配*表示*成本时，自适应Nyström可能更精确，但代价是数据依赖且非流式），并在一项控制测试中显示，\(\tifinaghfont{ⵟ}\)核在耦合对齐–接近性目标上优于单因子控制的对照情形。  

## 1 引言  
核方法（支持向量机 (Cortes & Vapnik,1995 (https://arxiv.org/html/2606.11255#bib.bib8))、核岭回归、高斯过程 (Rasmussen & Williams,2006 (https://arxiv.org/html/2606.11255#bib.bib22))，以及现代Transformer的注意力层（它对token计算核平滑器 (Tsai et al.,2019 (https://arxiv.org/html/2606.11255#bib.bib28))））依赖于\(N\times N\)的Gram矩阵\(K_{ij}=k(x_i,x_j)\)，其\(O(N^2)\)存储和\(O(N^3)\)分解在\(N\)超过\(10^5\)时变得不可行。核可以是固定的或通过隐式学习得到 (Li et al.,2019 (https://arxiv.org/html/2606.11255#bib.bib13))，但无论如何，扩展这些方法意味着永远不显式构造\(K\)，而主要工具是随机特征映射：一个低维的\(z\)满足\(\mathbb{E}[z(x)^\top z(w)]=k(x,w)\)，从而使\(K\approx ZZ^\top\)能在\(O(NM)\)时间和内存中处理。对于注意力机制，这对应随机特征线性注意力路径 (Katharopoulos et al.,2020 (https://arxiv.org/html/2606.11255#bib.bib12); Choromanski et al.,2021 (https://arxiv.org/html/2606.11255#bib.bib7))。哪些核允许这样的映射取决于其结构。  
*随机傅里叶特征* (RFF) (Rahimi & Recht,2007 (https://arxiv.org/html/2606.11255#bib.bib23)) 通过Bochner定理覆盖平移不变核\(k(x,w)=\phi(x-w)\)，采样非负谱测度（其傅里叶变换为\(\phi\)）；拟蒙特卡洛 (Avron et al.,2016 (https://arxiv.org/html/2606.11255#bib.bib3)) 和正交频率 (Yu et al.,2016 (https://arxiv.org/html/2606.11255#bib.bib34)) 降低其方差，该构造支撑大规模核岭回归 (Avron et al.,2017 (https://arxiv.org/html/2606.11255#bib.bib4))。  
*多项式草图*和点积随机特征（TensorSketch、Fastfood以及Pham & Pagh (2013) (https://arxiv.org/html/2606.11255#bib.bib19)、Le et al. (2013) (https://arxiv.org/html/2606.11255#bib.bib17)、Kar & Karnick (2012) (https://arxiv.org/html/2606.11255#bib.bib14) 的点积特征映射）对点积核\(k(x,w)=\kappa(x^\top w)\)做同样处理。  
*Nyström方法* (Williams & Seeger,2000 (https://arxiv.org/html/2606.11255#bib.bib32); Musco & Musco,2017 (https://arxiv.org/html/2606.11255#bib.bib18)) 走另一条路，从\(m\ll N\)个地标列构建低秩近似，其效果取决于核的谱衰减。每个族都绑定于一种结构：RFF对应平移不变性，草图对应点积形式，Nyström对应快速特征值衰减。一个统一线索是，任何可写成*混合*形式的核都可以通过混合采样来线性化，这使RFF扩展到高斯谱以外的宽平稳族 (Wilson & Adams,2013 (https://arxiv.org/html/2606.11255#bib.bib33))；我们的径向因子正是以这种方式处理。这里特殊之处在于，混合仅应用于一个*并非*整体平稳的核的径向部分，并且与多项式部分的精确有限特征组合，因此该方案位于基于混合的RFF与精确特征映射的交汇处，而不属于其中任一。  
我们希望扩展的核不符合这些模式。有偏\(\tifinaghfont{ⵟ}\)核  
\[
k_{\text{\tifinaghfont ⵟ},b}(w,x)=\frac{(w^\top x+b)^2}{\|w-x\|^2+\varepsilon},\qquad b\ge 0,\ \varepsilon>0,
\]
耦合了对齐性和接近性：分子是平方内积，分母是反平方距离。命题A.9 (https://arxiv.org/html/2606.11255#A1.Thmtheorem9) 中的有限差分恒等式表明，族\(\operatorname{span}\{k_{\text{\tifinaghfont ⵟ},b}:b\ge 0\}\)包含反多二次 (IMQ) 核。本文不依赖任何单核普适性陈述；固定\(b>0\)的普适性由Bouhsine (2026) (https://arxiv.org/html/2606.11255#bib.bib6) 单独讨论。在构造和实验中，我们将固定\(b>0\)视为实用的归纳偏置参数，而无偏\(k_{\text{\tifinaghfont ⵟ}}\)（\(b=0\)，其RKHS函数均在原点为零）是特例。  
但\(k_{\text{\tifinaghfont ⵟ},b}\)*不是*平移不变的，也*不是*点积核：径向分母\(\|x-w\|^2\)单独是平移不变的，然而乘上对齐分子\((x^\top w+b)^2\)同时破坏了两种形式，因此对完整核既不能应用Bochner采样也不能应用多项式草图，而精确方法退回到\(O(N^2)\)的Gram矩阵。（在单位球面上，\(\|x-w\|^2=2-2x^\top w\)，因此\(k_{\text{\tifinaghfont ⵟ},b}\)与有理点积核重合，此时可得到维度高效的点积路径；推导该路径留作未来工作，本文针对一般的\(\mathbb{R}^d\)构造，其中不存在这种约化。）关键实证测试因此是在球外（图1 (https://arxiv.org/html/2606.11255#S1.F1)）：在有界球上（范数可变，见第4.1节 (https://arxiv.org/html/2606.11255#S4.SS1)），该核真正非点积型，而RAY（\(\tifinaghfont{ⵟ}\)核的随机近似）保持\(O(1/\sqrt{D})\)行为，而地标方法随\(d\)退化。  
一旦将\(k_{\text{\tifinaghfont ⵟ},b}\)解读为两个个别易处理部分的Schur积（式(2) (https://arxiv.org/html/2606.11255#S2.E2)），障碍便消解：有偏二次多项式核\((w^\top x+b)^2\)具有精确有限特征映射，而IMQ型径向核\((\|w-x\|^2+\varepsilon)^{-1}\)在\(\|x-w\|^2\)上完全单调，因此是高斯分布关于单一尺度参数的Bernstein–Widder混合（经典Schoenberg径向核 (Schoenberg,1938 (https://arxiv.org/html/2606.11255#bib.bib25))，对此存在超出此IMQ情形的宽尺度混合采样器 (Langrené et al.,2024 (https://arxiv.org/html/2606.11255#bib.bib16))）。我们将其转化为一个*两个因子均随机化*的特征方案：采样径向因子的一维尺度，对得到的应用高斯随机傅里叶特征，并对多项式因子进行草图采样。保持多项式精确是可分析极限（\(m\to\infty\)），此时方差和集中性最尖锐；但该特征带有\(O(d^2)\)的多项式大小，而草图使维度变为\(Dm\)，摆脱了\(d^2\)，代价是一个可控的附加草图项（定理3.4 (https://arxiv.org/html/2606.11255#S3.Thmtheorem4)）。除了径向随机傅里叶特征之外，仅有的附加随机性是Bernstein一维尺度，因此对于固定数据集，径向抽取次数不显含\(d\)依赖（与标准RFF相同），这与均匀Nyström形成真正对比（我们确认后者随\(d\)退化）。要点不在于核的乘积可以张量化（这是标准闭包性质），而在于将这个特定的非平稳、非点积核分解，使每个部分变成教科书对象（一个精确有限多项式特征和一个高斯混合），从而一个不符合任一随机特征模板的核通过组合各自的标准工具得以线性化。这使RAY跻身于超越Bochner采样的随机特征方法之列：对于点积 (Kar & Karnick,2012 (https://arxiv.org/html/2606.11255#bib.bib14); Pham & Pagh,2013 (https://arxiv.org/html/2606.11255#bib.bib19))、组合 (Daniely et al.,2017 (https://arxiv.org/html/2606.11255#bib.bib9)) 以及非平稳谱或可调和核 (Remes et al.,2017 (https://arxiv.org/html/2606.11255#bib.bib21); Ton et al.,2018 (https://arxiv.org/html/2606.11255#bib.bib27); Shen et al.,2019 (https://arxiv.org/html/2606.11255#bib.bib26))，其不同之处在于将核分解为有限调制和完全单调径向因子，并分别用其原生工具（多项式草图和Bernstein–Widder径向采样器，第5节 (https://arxiv.org/html/2606.11255#S5)）随机化。  
本文的贡献是对所得的估计量及其定义的核类进行分析。对于精确调制，我们证明无偏性、平坦估计量的精确方差、由核和调制Gram矩阵的顶部特征值连同内在维度控制的期望矩阵Bernstein算子范数界（附带匹配尾界），以及相对谱核岭稳定性；对草图取条件可将算子范数保证传递给部署的双重随机化估计量。无偏性、方差和均匀逐项界可直接提升至*Bernstein–Schur*类（一个有限特征核乘以一个完全单调径向核，其中\(k_{\text{\tifinaghfont ⵟ},b}\)是旗舰实例），只需一个定理即可（定理2.5 (https://arxiv.org/html/2606.11255#S2.Thmtheorem5)）；我们为\(k_{\text{\tifinaghfont ⵟ},b}\)证明了矩阵Bernstein和核岭回归的结论，其证明模式适用于任何有界有限调制。构造本身是自明的：通过Schur分解（式(2) (https://arxiv.org/html/2606.11255#S2.E2)）的正定性，有限差分恒等式（命题A.9 (https://arxiv.org/html/2606.11255#A1.Thmtheorem9)）给出的IMQ族，以及Bernstein–Widder的径向混合（第2.2节 (https://arxiv.org/html/2606.11255#S2.SS2)）；我们仅借用Bouhsine (2026) (https://arxiv.org/html/2606.11255#bib.bib6) 的历史无限特征解释和本文不需要的固定\(b\)普适性。  

#### 贡献。  
1. (i) 针对一个核类（而非一个核）的随机特征构造。我们识别出*Bernstein–Schur核*（有限特征核乘以完全单调平移不变核），并为整个核类给出一个估计量：保持有限特征精确，采样径向Bernstein–Widder尺度，并应用随机傅里叶特征（定理2.5 (https://arxiv.org/html/2606.11255#S2.Thmtheorem5)，包含无偏性、方差和均匀界）。有偏\(\tifinaghfont{ⵟ}\)核是旗舰实例（第2节 (https://arxiv.org/html/2606.11255#S2)，命题2.1 (https://arxiv.org/html/2606.11255#S2.Thmtheorem1) 显示它真正既非平稳也非点积）；部署的估计量对两个因子均随机化，精确调制为可分析极限（第2.5节 (https://arxiv.org/html/2606.11255#S2.SS5)）。  
2. (ii) 尖锐方差与最优分配（第3节 (https://arxiv.org/html/2606.11255#S3)）：推荐平坦估计量的*精确*方差（定理3.1 (https://arxiv.org/html/2606.11255#S3.Thmtheorem1)）、一个两层恒等式证明在分层估计量中、在固定径向特征预算下每尺度单频率方差最优（命题A.2 (https://arxiv.org/html/2606.11255#A1.Thmtheorem2)），以及一个方差有界（与数据半径和偏置无关）的归一化变体（命题A.7 (https://arxiv.org/html/2606.11255#A1.Thmtheorem7)）。  
3. (iii) Gram矩阵集中性与确定性KRR扰动稳定性：均匀Gram界（定理A.3 (https://arxiv.org/html/2606.11255#A1.Thmtheorem3)）和期望矩阵Bernstein算子范数界（定理3.2 (https://arxiv.org/html/2606.11255#S3.Thmtheorem2)），附带匹配的高概率尾界（推论3.3 (https://arxiv.org/html/2606.11255)