Optimally-Weighted Herding is Bayesian Quadrature

问题陈述
统计机器学习中的一个基本挑战是计算函数在概率分布上的期望，表示为 $Z_{f,p} = \int f(x)p(x)dx$。虽然蒙特卡洛方法通过随机采样以 $O(1/\sqrt{N})$ 的收敛速率进行近似，但它们受限于随机方差。拟蒙特卡洛方法通过生成伪样本提供了一种确定性的替代方案，旨在最小化样本的经验分布与目标分布 $p(x)$ 之间的差异（Discrepancy）。两种著名的确定性方法是核赫尔丁法（Kernel Herding），它通过最小化最大均值差异（MMD）来选择样本，以及贝叶斯求积法（Bayesian Quadrature, BQ），它通过推断函数 $f$ 的后验分布来估计积分。本文探讨了这两种方法之间的理论联系，并研究了加权采样方法是否能优于标准的赫尔丁法。

方法论
作者通过分析每种方法所最小化的目标函数，建立了核赫尔丁法与贝叶斯求积法之间的理论联系。

1. 准则等价性： 本文证明了核赫尔丁法中最小化的准则（MMD）在假设 $f$ 服从高斯过程（GP）先验的情况下，在数学上等价于贝叶斯求积法中积分估计的后验方差。具体而言，BQ 中的预期误差对应于目标分布 $p$ 与由样本及其权重定义的离散分布之间的 MMD。
2. 序列贝叶斯求积（SBQ）： 虽然标准的赫尔丁法为样本分配均匀权重（$1/N$），但 BQ 会分配由 GP 后验导出的最优权重。作者提出了序列贝叶斯求积（SBQ），这是一种贪婪算法，通过选择样本位置来最小化后验方差（等价于使用最优权重最小化 MMD）。
3. 权重分析： 本文分析了 BQ 权重的性质，指出它们不一定为正，且其和不一定为一。这些权重被证明在由核定义的再生核希尔伯特空间（RKHS）内具有极小极大（minimax）意义下的最优性。
4. 次模性（Submodularity）： 作者通过将样本选择过程与稀疏字典选择问题联系起来，研究了 SBQ 的收敛性质。他们证明了该目标函数是“近似次模”的，从而可以为贪婪选择策略提供理论性能界限，尽管这些界限比严格次模函数的界限要弱。

核心贡献

1. 理论统一： 本文证明了核赫尔丁法所最小化的损失与贝叶斯求积法的预期误差（后验方差）是相同的。因此，BQ 被构架为一种加权版本的核赫尔丁法，其中权重对于给定的 RKHS 是最优的。
2. 权重的最优性： 研究表明，由 BQ 导出的权重在收敛速率方面优于均匀加权的赫尔丁法和其他非最优加权的赫尔丁法。
3. 算法联系： 该工作将 BQ 中的贪婪样本选择与稀疏字典选择问题联系起来，确立了该目标函数是近似次模的。
4. 实证验证： 作者提供了实证证据，表明 SBQ 的收敛速率快于 $O(1/N)$，在最大均均值差异（MMD）和积分估计误差方面均优于标准赫尔丁法和独立同分布（i.i.d.）随机采样。

结果

• 收敛速率： 在使用二维高斯混合模型的实验中，SBQ 展示了优于赫尔丁法在有限维空间中通常具有的 $O(1/N)$ 的收敛速率。虽然 SBQ 在无限维空间中的确切理论速率尚不明确，但实验结果表明其速度快于 $O(1/N)$。
• 样本效率： 本文说明，少量 SBQ 样本（例如 8 个）配合最优权重，即可达到与大量赫尔丁法样本（例如 20 个）配合均匀权重相同的估计误差。
• 鲁棒性： 在针对超出假设 RKHS 的函数的实验中显示，尽管理论保证依赖于函数属于该 RKHS，但各方法的相对性能排名（SBQ > Herding > i.i.d.）即使对于“模型外”函数也保持一致。
• 误差界限： MMD 为 BQ 估计的经验误差提供了一个可证明的上界，该上界显示随样本数量增加而迅速减小。

意义与主张
本文声称，序列贝叶斯求积通过将最优权重集成到样本选择过程中，代表了相对于核赫尔丁法的显著进步。通过将 BQ 视为一种最优加权的赫尔丁法，作者提供了一个统一的理论框架，解释了 BQ 表现更优的原因。该工作强调，虽然 BQ 的计算成本较高（权重计算为 $O(N^3)$，而赫尔丁法为 $O(N^2)$），但其更快的收敛速率可能使其在函数评估成本较高的场景中更具效率。作者谦虚地指出，虽然他们建立了经验误差的上界并实证展示了快于 $O(1/N)$ 的收敛，但 SBQ 在无限维空间中的理论最优收敛速率仍是未来研究中一个开放的问题。文章总结道，方法的选择取决于计算成本与被积函数 $f$ 评估成本之间的权衡。