State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives¶

会议: NeurIPS 2026
arXiv: 2605.13127
OpenReview: https://openreview.net/forum?id=D8tqZupi52
领域: 其他
关键词: 确定性点过程, 小波核, 离散化投影, 小批量采样, 粗糙目标函数

一句话总结¶

本文提出了基于多分辨率正交小波基的全新连续确定性点过程（DPP）核，将 $C^1$ 目标函数线性统计量的标准误衰减率提升至最优的 $O(n^{-(1/2 + 1/d)})$ 并自适应扩展至粗糙目标函数（Hölder 与分数阶 Sobolev 空间），同时建立了通用的连续到离散低秩核转换管线，以 $O(Nn^2 + n^3)$ 极低采样复杂度将方差缩减优势严格无损传递到离散小批量与核集（Coreset）构建中。

研究背景与动机¶

在大规模机器学习中，随机梯度下降（SGD）的小批量（Minibatch）抽取、核集（Coreset）压缩以及数值求积等任务，通常依赖于对完整数据集的子采样。传统的独立同分布（i.i.d.）均匀采样受制于中心极限定理，其估计量的标准误仅能达到经典的蒙特卡洛率 $O(1/\sqrt{n})$，且易由于样本聚集导致冗余。为了降低采样方差，具有排斥性质的确定性点过程（Determinantal Point Processes, DPPs）近年来被引入机器学习。现有的主流构造主要依赖多元正交多项式系（Multivariate Orthogonal Polynomial Ensembles, OPEs），在目标函数满足连续可微（$C^1$）假设时，能将标准误提升至 $O(n^{-(1/2 + 1/(2d))})$。

然而，现有基于 DPP 的小批量与核集构建方案面临两个根本瓶颈。其一是核函数的方差缩减理论受限于光滑性假设：实际机器学习中的损失函数往往具有粗糙性（Roughness）甚至不可导性（例如支持向量机中的 Hinge 损失、含 ReLU 的深度网络以及金融时间序列数据），现有 OPE 核缺乏对低正则性（如 Hölder 连续或分数阶 Sobolev 空间）目标函数的方差缩减保证，在粗糙目标下甚至退化严重。其二是“连续到离散”的鸿沟难以兼顾理论保证与计算效率：理论上易于分析方差性质的 DPP 均定义在连续欧氏空间中，但机器学习数据集是离散集合，过往将连续 DPP 迁移到离散数据集的方法（如截断投影或特定离散正交多项式构造）不仅计算代价极高（涉及对近乎满秩的 $N \times N$ 矩阵进行谱截断），而且需要复杂的特例化推导，缺乏通用的方差传递保证。

针对上述瓶颈，本文希望建立一套兼具最优方差衰减率、适应粗糙目标函数且支持高效离散采样的 DPP 工具箱。核心 idea：利用多分辨率分析构造紧支撑正交小波投影核，使连续 DPP 的方差衰减率紧致自适应于目标函数的粗糙度（在 $C^1$ 下达到最优的 $O(n^{-(1/2 + 1/d)})$ 标准误）；同时设计一种基于矩阵低秩分解的通用“连续到离散”转换机制，在保证 $O(Nn^2 + n^3)$ 准线性采样复杂度的同时，显式证明离散小批量能够无损继承连续核的方差缩减阶数。

方法详解¶

整体框架¶

本文方法的流水线包含三大协同阶段：连续小波核设计、连续至离散的低秩映射采样、以及针对非均匀边界波动的控制变量估计。首先，在连续背景空间 $\mathbb{R}^d$ 上，利用多分辨率分析中的紧支撑正交尺度函数（如 Haar 尺度函数或 Daubechies 尺度函数）张量积构建尺度为 $2^{-j}$ 的连续投影核 $K$；其次，给定规模为 $N$ 的离散数据集 $\mathcal{X}$，计算样本在连续核前 $n$ 个正交特征基下的特征矩阵 $\mathbf{\Psi} \in \mathbb{R}^{N \times n}$，并通过数据概率密度（或其核密度估计 KDE）加权构造离散 $L$-ensemble 矩阵 $\mathbf{L}$，利用低秩性质在 $O(Nn^2 + n^3)$ 时间内精确抽取大小为 $m \leq n$ 的离散子集 $\mathcal{S}_d$；最后，根据连续核对角线是否恒定，采用直接对角加权或控制变量修正的线性统计量估计全量经验损失与次梯度。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["连续背景空间与粗糙目标函数<br/>f ∈ C^{0,s} 或 H^s"] --> B["正交小波投影核设计<br/>MRA多分辨率分析 + 紧支撑尺度函数"]
    B --> C["连续小波DPP采样器<br/>方差衰减达到最优 O(n^{1-2s/d})"]
    D["规模为N的大规模数据集 𝒳<br/>经验分布 / KDE估计密度 ρ̂"] --> E["连续至离散保方差转换管线<br/>特征矩阵 Ψ 与低秩 L-ensemble 分解"]
    C -.->|理论方差保界传递| E
    E --> F["快速特征分解与离散采样<br/>计算代价 O(Nn^2 + n^3) 抽取子集 S_d"]
    F --> G["控制变量调整估计子<br/>消除边界与核对角波动，输出无偏估计"]
    G --> H["下游ML任务应用<br/>SGD非光滑优化 / k-means核集压缩"]

关键设计¶

1. 正交小波投影核设计：突破光滑性限制的高阶方差缩减机制 传统 OPE 核以全局正交多项式作为基函数，当目标函数在局部存在奇异点或不可导时，多项式逼近容易出现吉布斯效应，导致方差衰减严重受阻。为了克服这一痛点，本文利用紧支撑正交多分辨率分析（Multiresolution Analysis, MRA）中的一维尺度函数 $\phi: \mathbb{R} \to \mathbb{R}$（满足 $\int \phi(x) dx = 1$），在尺度 $j \in \mathbb{N}$ 下通过张量积构建 $d$ 维基函数 $\Phi_{-j, \mathbf{k}}(\mathbf{x}) = \prod_{i=1}^d 2^{dj/2} \phi(2^j x_i - k_i)$。在单位超立方体内部挑选支撑集落在 $[0, 1]^d$ 内的整点指标集合 $\mathcal{I}(j) = \{\mathbf{k} \in \mathbb{Z}^d : \mathrm{supp}(\Phi_{-j, \mathbf{k}}) \subset [0, 1]^d\}$，定义连续投影核： $$K(\mathbf{x}, \mathbf{y}) = \sum_{\mathbf{k} \in \mathcal{I}} \Phi_{-j, \mathbf{k}}(\mathbf{x}) \Phi_{-j, \mathbf{k}}(\mathbf{y})$$ 该核的秩为 $n = |\mathcal{I}(j)| \asymp 2^{dj}$。由于小波基函数具备优异的空间局域化与多尺度逼近特性，对于属于 Hölder 连续空间 $C^{0,s}$ 或分数阶 Sobolev 空间 $H^s$（正则度指数 $s \in (0, 1]$）的目标函数 $f$，其线性统计量 $\Lambda_{\mathcal{S}_c}(f) = \sum_{Y \in \mathcal{S}_c} f(Y)$ 的方差满足： $$\mathrm{Var}[\Lambda_{\mathcal{S}_c}(f)] \leq C |f|_s^2 n^{1 - 2s/d}$$ 特别地，当 $s=1$（Lipschitz 或 $C^1$ 函数）时，方差为 $O(n^{1 - 2/d})$，标准误达到 $O(n^{-(1/2 + 1/d)})$，显著优于传统 OPE 的 $O(n^{-(1/2 + 1/(2d))})$，在无需紧复流形等严苛代数几何前提下，达到了当前连续点过程理论中的最快衰减速度；此外，当采用 Haar 小波时，该连续核恰好等价于连续分层抽样（Stratified Sampling），从而从理论上首次严格统一了分层抽样与 DPP 的数理机制。

2. 连续至离散保方差转换管线：低秩分解驱动的轻量化离散 DPP 构建 此前将连续 DPP 移植到离散数据集上的方法，往往需要求解尺寸为 $N \times N$ 的核矩阵截断或重构，计算复杂度高达 $O(N^3)$，难以处理数十万规模的数据。针对该计算与理论断层，本文提出了通用的开箱即用转换机制。设数据集 $\mathcal{X} = \{X_1, \dots, X_N\}$ 独立同分布采样自概率密度 $\rho(x)$（未知时可用核密度估计 $\hat{\rho}$ 替代），计算连续核对应的 $n$ 个特征基在离散样本上的取值矩阵 $\mathbf{\Psi} = [\psi_k(X_i)] \in \mathbb{R}^{N \times n}$，并定义离散 $L$-ensemble 矩阵： $$\mathbf{L} = \frac{1}{N} \mathbf{D}(\rho^{-1/2}) \mathbf{\Psi} \mathbf{\Psi}^\top \mathbf{D}(\rho^{-1/2}) = \mathbf{B} \mathbf{B}^\top, \quad \mathbf{B} = \frac{1}{\sqrt{N}} \mathbf{D}(\rho^{-1/2}) \mathbf{\Psi} \in \mathbb{R}^{N \times n}$$ 通过限制子集大小为 $m = \mathrm{rank}(\mathbf{\Psi}) \leq n$ 得到离散 $m$-DPP $\mathcal{S}_d$。本文严格证明了 $\mathcal{S}_d$ 本质上是投影到 $\mathbf{L}$ 特征向量空间的离散投影 DPP。由于 $\mathbf{B}$ 为 $N \times n$ 的低秩矩阵，其非零特征值与特征向量可通过对 $n \times n$ 的小矩阵 $\mathbf{B}^\top \mathbf{B} = \frac{1}{N} \mathbf{\Psi}^\top \mathbf{D}(\rho^{-1}) \mathbf{\Psi}$ 进行特征分解直接获得，使得整套采样算法的时间复杂度大幅压缩至 $O(Nn^2 + n^3)$。更为关键的是，定理 3.2 证明了该离散子集关于全数据集的条件方差严格受到连续核方差的双向夹逼： $$\frac{N-1}{2N} \mathrm{Var}[\Lambda_{\mathcal{S}_c}(f)] - \text{error} \leq \mathrm{Var}[\Lambda_{\mathcal{S}_d}(f) | \mathcal{X}] \leq 2 \mathrm{Var}[\Lambda_{\mathcal{S}_c}(f)] + \text{error}$$ 其中误差项完全显式且以高概率随 $O(n^2 / \sqrt{N})$ 快速收缩，在 $N \gg n$ 的实际深度学习或大数据场景下完全可以忽略，从而实现了方差递减性质从连续理论到离散工程的严密保界传递。

3. 控制变量调整估计子：消除核对角与非均匀边界波动的统计量修正 对于经典的 Haar 尺度函数，其核矩阵对角线元素在支撑集内为常数（$K(x, x) = n$）；然而，对于平滑的高阶小波（如常用且具备紧支撑、正交性的 Daubechies-2 / db2 小波），核的对角线值 $K(x, x)$ 在空间中存在非均匀波动与边界衰减，若直接采用倒数加权估计子 $\mathcal{L}_{\mathcal{S}}(f) = \sum_{Y \in \mathcal{S}} \frac{f(Y) \omega(Y)}{K(Y, Y)}$，会导致估计方差中混入高阶局部扰动项。为此，本文受蒙特卡洛控制变量（Control Variates）思想启发，在每个微小网格单元 $\mathrm{supp}(\Phi_{-j, \mathbf{k}})$ 内锚定一个固定参考点 $\mathbf{x}_{\mathbf{k}}$，设计了调整估计子： $$\widetilde{\mathcal{L}}_{\mathcal{S}_c}(f) := \mathcal{L}_{\mathcal{S}_c}(f) - \frac{1}{2^{dj/2}} \sum_{i=1}^n \sum_{\mathbf{k} \in \mathcal{I}} \frac{\Phi_{-j, \mathbf{k}}(Y_i)}{K(Y_i, Y_i)} f(\mathbf{x}_{\mathbf{k}}) \omega(\mathbf{x}_{\mathbf{k}}) + \frac{1}{2^{dj}} \sum_{\mathbf{k} \in \mathcal{I}} f(\mathbf{x}_{\mathbf{k}}) \omega(\mathbf{x}_{\mathbf{k}})$$ 该设计通过引入确定性网格求和作为方差基准抵消项，巧妙对冲了基函数在边界和局部重叠处的震荡。仅需付出增加至多 $2n$ 次函数求值的极低计算代价，即可在任意通用平滑尺度函数下，将目标函数的均方误差（MSE）牢牢稳定在最优的 $O(n^{-1 - 2s/d})$，彻底释放了平滑小波在复杂数据集上的高阶抗噪性能。

损失函数 / 训练策略¶

在机器学习小批量优化场景下，本文重点验证了非光滑目标函数下的随机次梯度下降。以经典的 Pegasos 算法（优化支持向量机 Hinge 损失 $\ell(\theta; x_i, y_i) = \max(0, 1 - y_i \langle \theta, x_i \rangle)$）为例，其在迭代步 $t$ 处的次梯度更新目标为： $$\theta_{t+1} = \theta_t - \eta_t \nabla_t, \quad \nabla_t = \lambda \theta_t + \frac{1}{|\mathcal{S}_d|} \sum_{i \in \mathcal{S}_d} \mathbf{1}\{y_i \langle \theta_t, x_i \rangle < 1\} y_i x_i$$ 其中步长设定为 $\eta_t = 1 / (\lambda t)$，正则化参数 $\lambda = 0.1$。每轮采样时，从两类平衡数据集（各抽样本 $m/2$）中利用离散小波 DPP 快速抽取样本大小为 $m=32$ 的代表性子集 $\mathcal{S}_d$。由于 Hinge 损失在判决边界处不可导（仅属于 Lipschitz 连续 / $C^{0,1}$ 粗糙函数），小波核提供的主导方差缩减使得随机次梯度 $\nabla_t$ 相较于全批量梯度的残差方差显著压低，极大地削弱了随机抖动并加速收敛至全局最优点 $\theta^*$。

实验关键数据¶

主实验¶

论文在两类代表性机器学习任务中开展了实证评估：首先是在 $k$-means 聚类的核集（Coreset）压缩任务中对比 5 种采样策略（i.i.d. 均匀采样、基于经验测度的离散 OPE vdm-dpp、连续到离散 OPE ope、Haar 小波核 haar 以及周期化 Daubechies-2 小波核 db2）；评估指标为 150 次独立重复试验中核集相对误差的上确界 90% 分位数 $Q_{\mathcal{S}}(0.9)$。数据集采用合成三峰高斯混合分布（Trimodal, $N=1024, k=3$）与 PCA 降维至 $d=2$ 的 MNIST 数据集（$k=10$）。其次是在 MNIST 二分类（数字 4 与 9，降至 $d=2$，$N=1000$）上采用 Pegasos 求解非光滑 Hinge 损失 SVM，比较测试误差、全批量次梯度范数与参数收敛误差。

任务 / 数据集	采样规模 ($m$)	i.i.d. (基线)	OPE 变体 (`vdm` / `ope`)	Haar 小波 (`haar`)	Daubechies-2 (`db2`, 本文)	性能提升说明
$k$-means MNIST ($d=2$)	$m=16$	0.82	0.61 (`vdm`) / 0.65 (`ope`)	0.49	0.42	相对误差相比 i.i.d. 减半，显著优于 OPE
$k$-means MNIST ($d=2$)	$m=32$	0.58	0.42 (`vdm`) / 0.45 (`ope`)	0.31	0.26	误差持续保持各方法中最低
$k$-means MNIST ($d=2$)	$m=64$	0.41	0.28 (`vdm`) / 0.30 (`ope`)	0.20	0.16	展现出更陡峭的方差随 $m$ 衰减趋势
$k$-means Trimodal ($d=2$)	$m=32$	0.52	0.34 (`vdm`) / 0.36 (`ope`)	0.35	0.24	db2 鲁棒性最优，haar 在多峰时退化至 OPE
Pegasos SVM (200步测试误差)	$m=32$	9.4% (±1.2%)	7.8% (±0.9%)	6.7% (±0.7%)	5.9% (±0.6%)	分类错误率下降 3.5 个百分点
Pegasos 梯范数 $\\|\nabla f(\theta_t)\\|_2$	$m=32$	0.34 (波动剧烈)	0.21 (中等波动)	0.16 (轻微波动)	0.12 (极平稳收敛)	随机次梯度方差大幅削减，贴近全批量
*Pegasos 参数误差 $\\|\theta_t - \theta^\\|_2$**	$m=32$	0.28	0.17	0.13	0.09	最快逼近 Scikit-learn 精确参考解

消融实验¶

论文在附录中针对一维与二维空间下的粗糙函数积分（Quadrature）进行了不同正则性目标函数的方差收敛阶消融测试。选取具有显式 Hölder/Sobolev 指数的 4 类测试函数：极度粗糙函数 $\varphi_{0.25} \in C^{0, 0.25}$、中度粗糙函数 $\varphi_{0.75} \in C^{0, 0.75}$、非光滑 Lipschitz 函数 $\varphi_{\text{mixcos}} \in C^{0, 1}$ 以及无穷光滑函数 $\varphi_{\text{bump}} \in C^\infty$。在 100 次重复试验下统计方差相对于样本量 $n$ 的双对数衰减斜率。

测试目标函数	理论正则度	传统 i.i.d. 衰减率	Dirichlet 核 (`dir`)	OPE 多项式核 (`ope`)	本文小波核 (`haar` / `db2`)	消融与机制说明
粗糙幂次 $\varphi_{0.25}$ ($d=1$)	$s = 0.25$	$O(n^{-1.00})$	$O(n^{-1.28})$	$O(n^{-1.24})$	$O(n^{-1.50})$	严格贴合理论界 $n^{-1-2s/d}$，小波优势最悬殊
粗糙幂次 $\varphi_{0.75}$ ($d=1$)	$s = 0.75$	$O(n^{-1.00})$	$O(n^{-1.65})$	$O(n^{-1.61})$	$O(n^{-2.48})$	方差衰减斜率显著超越现有所有核结构
非可微 Lipschitz $\varphi_{\text{mixcos}}$ ($d=1$)	$s = 1.0$	$O(n^{-1.00})$	$O(n^{-1.92})$	$O(n^{-1.90})$	$O(n^{-2.95})$	接近 $O(n^{-3})$ 极限率，OPE 仅在 $O(n^{-2})$ 停滞
无穷光滑 $\varphi_{\text{bump}}$ ($d=1$)	$s = \infty$	$O(n^{-1.00})$	$O(n^{-2.10})$	$O(n^{-3.20})$	$O(n^{-3.00})$	光滑极端下 OPE 占优，证明小波专精粗糙域
二维粗糙 $\varphi_{0.25}$ ($d=2$)	$s = 0.25$	$O(n^{-1.00})$	$O(n^{-1.12})$	$O(n^{-1.11})$	$O(n^{-1.25})$	在 $d=2$ 下依然严格保持对基线与 OPE 的领先

关键发现¶

小波基函数具备卓越的抗粗糙性：在目标函数不可导或仅具备低阶 Hölder 连续性时，小波核（特别是带有平滑过渡的 db2）的方差衰减率优势最为突出；而在传统 OPE 擅长的无穷光滑区域，多项式逼近虽略占微弱优势，但小波核依然能达到匹敌的超线性收敛。
平滑尺度函数的综合鲁棒性强于阶梯状 Haar：在多峰分布（Trimodal）下，Haar 核的阶跃硬边界无法平滑过渡，性能衰减至接近 OPE 水平；而带有重叠平滑支撑的 db2 配合控制变量估计子，在复杂几何流形和聚类结构上均展现出绝对的泛化优势。
离散采样极具工程落地价值：得益于 $\mathbf{\Psi} \mathbf{\Psi}^\top$ 的低秩结构，小批量抽样耗时基本与全数据规模 $N$ 呈严格线性关系，在 1000 个样本上抽取 $m=32$ 小批量仅耗费毫秒级时间，完全满足在 SGD 迭代流中动态采样的效率要求。

亮点与洞察¶

将经典分层抽样统一收敛为 DPP 的特例：证明了当选取一维 Haar 尺度函数时，连续小波投影 DPP 在数学分布上与欧氏网格空间中的均匀分层抽样完全重合。这不仅在理论上为分层抽样提供了全新的排斥点过程解释，更通过小波多分辨率框架为分层抽样向任意非平凡平滑核的推广铺平了道路。
轻量低秩映射彻底破解连续理论与离散工程的脱节：过去连续点过程的优异方差界往往难以落地，症结在于缺乏计算友好的离散化机制。本文构造的 $\mathbf{L} = \frac{1}{N} \mathbf{D}(\rho^{-1/2}) \mathbf{\Psi} \mathbf{\Psi}^\top \mathbf{D}(\rho^{-1/2})$ 构造不仅将 $N \times N$ 特征分解转换为 $n \times n$ 内积特征分解，还给出了全显式（含常数）的高概率误差界，为机器学习领域设计连续先验离散落地的算法提供了通用范式。
为非光滑深层优化的 Minibatch 提供了扎实的理论支点：现有深度学习大量使用 ReLU、分段线性函数以及稀疏正则项，其理论性质一直被传统光滑分析所忽视。本工作的方差界明确将收敛速度绑定在目标函数的 Hölder 指数 $s$ 上，为非平滑目标函数的随机小批量方差缩减确立了全新的标杆。

局限与展望¶

采样基数随特征维度呈指数级膨胀：由于小波核基于张量积构造，投影空间的秩 $n = |\mathcal{I}(j)| \asymp 2^{dj}$ 受到维度 $d$ 的指数限制。在未经降维的高维图像或文本嵌入中直接应用会导致小批量最小尺寸 $n$ 过大，因而当前必须依赖 PCA 或自编码器预先降维至低维潜在流形（如 $d \leq 4$）。
核密度估计在未知分布下的相对误差敏感性：定理 3.3 指出离散方差界依赖于密度估计相对误差 $\max_i |\rho(X_i)/\hat{\rho}(X_i) - 1| \leq \varepsilon$。在重尾分布或低密度边缘区域，KDE 的相对误差可能出现局部激增，需要进一步研究对局部密度估计鲁棒的加权正则化方案。
未来方向：探索非张量积的各向异性小波或树状多尺度基函数，以解耦点过程基数 $n$ 与维度 $d$ 的硬性绑定；将小波小批量采样推广到现代大语言模型微调中的指令子集选择或动态数据蒸馏管线中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将多分辨率小波分析与连续至离散保方差 DPP 理论统一，攻克了粗糙目标函数下的方差缩减瓶颈。
实验充分度: ⭐⭐⭐⭐ 涵盖数值求积、高斯混合聚类核集及 Pegasos 非光滑 SVM 分类，若能进一步在深层神经网络架构上验证端到端微调则更佳。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨精炼，连续到离散的引理与有限样本矩阵集中不等式衔接紧密，逻辑层次分明。
价值: ⭐⭐⭐⭐⭐ 为随机梯度下降小批量构建、核集压缩与非光滑优化提供了兼备最优理论阶数与准线性计算开销的基础数学工具箱。

测试目标函数	理论正则度	传统 i.i.d. 衰减率	Dirichlet 核 (`dir`)	OPE 多项式核 (`ope`)	本文小波核 (`haar` / `db2`)	消融与机制说明
粗糙幂次 \(\varphi_{0.25}\) (\(d=1\))	\(s = 0.25\)	\(O(n^{-1.00})\)	\(O(n^{-1.28})\)	\(O(n^{-1.24})\)	\(O(n^{-1.50})\)	严格贴合理论界 \(n^{-1-2s/d}\)，小波优势最悬殊
粗糙幂次 \(\varphi_{0.75}\) (\(d=1\))	\(s = 0.75\)	\(O(n^{-1.00})\)	\(O(n^{-1.65})\)	\(O(n^{-1.61})\)	\(O(n^{-2.48})\)	方差衰减斜率显著超越现有所有核结构
非可微 Lipschitz \(\varphi_{\text{mixcos}}\) (\(d=1\))	\(s = 1.0\)	\(O(n^{-1.00})\)	\(O(n^{-1.92})\)	\(O(n^{-1.90})\)	\(O(n^{-2.95})\)	接近 \(O(n^{-3})\) 极限率，OPE 仅在 \(O(n^{-2})\) 停滞
无穷光滑 \(\varphi_{\text{bump}}\) (\(d=1\))	\(s = \infty\)	\(O(n^{-1.00})\)	\(O(n^{-2.10})\)	\(O(n^{-3.20})\)	\(O(n^{-3.00})\)	光滑极端下 OPE 占优，证明小波专精粗糙域
二维粗糙 \(\varphi_{0.25}\) (\(d=2\))	\(s = 0.25\)	\(O(n^{-1.00})\)	\(O(n^{-1.12})\)	\(O(n^{-1.11})\)	\(O(n^{-1.25})\)	在 \(d=2\) 下依然严格保持对基线与 OPE 的领先

任务 / 数据集	采样规模 (\(m\))	i.i.d. (基线)	OPE 变体 (`vdm` / `ope`)	Haar 小波 (`haar`)	Daubechies-2 (`db2`, 本文)	性能提升说明
\(k\)-means MNIST (\(d=2\))	\(m=16\)	0.82	0.61 (`vdm`) / 0.65 (`ope`)	0.49	0.42	相对误差相比 i.i.d. 减半，显著优于 OPE
\(k\)-means MNIST (\(d=2\))	\(m=32\)	0.58	0.42 (`vdm`) / 0.45 (`ope`)	0.31	0.26	误差持续保持各方法中最低
\(k\)-means MNIST (\(d=2\))	\(m=64\)	0.41	0.28 (`vdm`) / 0.30 (`ope`)	0.20	0.16	展现出更陡峭的方差随 \(m\) 衰减趋势
\(k\)-means Trimodal (\(d=2\))	\(m=32\)	0.52	0.34 (`vdm`) / 0.36 (`ope`)	0.35	0.24	db2 鲁棒性最优，haar 在多峰时退化至 OPE
Pegasos SVM (200步测试误差)	\(m=32\)	9.4% (±1.2%)	7.8% (±0.9%)	6.7% (±0.7%)	5.9% (±0.6%)	分类错误率下降 3.5 个百分点
Pegasos 梯范数 \(\\|\nabla f(\theta_t)\\|_2\)	\(m=32\)	0.34 (波动剧烈)	0.21 (中等波动)	0.16 (轻微波动)	0.12 (极平稳收敛)	随机次梯度方差大幅削减，贴近全批量
*Pegasos 参数误差 \(\\|\theta_t - \theta^\\|_2\)**	\(m=32\)	0.28	0.17	0.13	0.09	最快逼近 Scikit-learn 精确参考解