Variational Free Energy Pivot Selection for Pivoted Cholesky

技术摘要：用于旋转 Cholesky 分解的变分自由能枢轴选择法

问题陈述
对称正定（SPD）矩阵的低秩近似在数值线性代数中至关重要，特别是在高斯过程（GP）回归中，其中核矩阵 $K$ 被近似为一个秩为 $r$ 的分解 $\tilde{K} = LL^\top$。经典的算法，如贪婪式和随机旋转 Cholesky（RPCholesky），通过顺序选择枢轴来最小化残差的代数迹范数误差（$\text{tr}(K - \tilde{K})$）。然而，在许多应用中，矩阵 $K$ 并非孤立地被评估，而是在一个非线性矩阵泛函内。具体而言，在高斯过程回归中，近似的质量由变分自由能（VFE）$L(\tilde{K})$ 决定，该函数是对数边际似然的一个下界。

VFE 泛函结合了三个截然不同的项：对数行列式项（复杂度）、二次数据拟合项以及迹惩罚项。现有的枢轴选择规则依赖于残差对角线的幅度，仅针对迹范数误差。因此，它们忽略了对数行列式和数据拟合部分，可能导致对于特定的推理目标产生系统性的次优近似。本文探讨的问题是：当目标是优化一个矩阵泛函而非纯粹的代数近似误差时，应当如何进行枢轴选择？

方法论
作者提出了一种新的枢轴选择规则，称为 $\Delta$-VFE 旋转 Cholesky，它直接最大化在 Cholesky 一致性秩-1 更新下，VFE 泛函的精确单步变化量。

1. 增益公式的推导：
   作者推导出了由秩-1 更新 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$ 引起的 VFE $L(\tilde{K})$ 的精确变化 $\Delta L$ 的闭式表达式。利用矩阵行列式引理和 Sherman-Morrison 公式，他们将增益分解为三个加性分量：
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   其中：

   • $a = u^\top \Sigma_i^{-1} u$ 代表复杂度贡献（对数行列式项），衡量更新与正则化逆度量之间的相互作用。
   • $b = u^\top \Sigma_i^{-1} y$ 代表数据拟合贡献，衡量更新方向与当前预测残差之间的对齐程度。
   • $\|u\|^2_2$ 代表迹贡献（残差方差减少），对应于精确的单步迹减少量，而非经典方法中使用的对角线代理。

2. Cholesky 一致性更新：
   为了确保近似保持为有效的 Cholesky 分解，更新向量 $u$ 被限制为形式 $u_p = t_p / \sqrt{(T_i)_{p,p}}$，其中 $t_p$ 是残差矩阵 $T_i$ 的第 $p$ 列。这种限制确保了残差保持半正定，并且所选枢轴的对角项变为零。

3. 算法实现：
   在每一步为所有 $n$ 个候选者评估 $\Delta L$ 在计算上是极其昂贵的（$O(n^2r^2)$）。为了保持效率，该方法采用了批量采样策略：

   • 在每次迭代中，从未使用的索引集中采样一个大小为 $s$ 的候选枢轴批次。
   • 采样概率与残差对角线条目成比例，这与 RPCholesky 使用的分布一致。
   • 利用 Woodbury 矩阵恒等式和辅助矩阵 $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$ 的增量更新，高效地应用正则化逆 $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$。
   • 这种方法允许以总成本 $O(snr^2)$ 评估 $s$ 个候选者的增益，其渐近复杂度在因子 $s$ 之外与 RPCholesky 保持一致。

核心贡献

• 面向目标的枢轴规则： 本文推导出了第一个显式最大化单步 VFE 增益的枢轴选择准则，而非仅仅是迹范数误差。
• 理论保证： 作者证明了任何 Cholesky 一致的秩-1 更新序列都会产生单调不减的 VFE 值序列。所提规则在每一步都选择能使该保证增益最大化的枢轴。
• 复杂度效率： 通过利用增量 Woodbury 更新和批量候选者评估，该方法实现了与随机化旋转 Cholesky 相同的渐近复杂度（$O(snr^2)$）。
• 层级解释： 该工作建立了三层枢轴规则的层级结构：
  1. 第一层： 经典贪婪/RPCholesky（使用对角线代理进行迹减少）。
  2. 第二层： 精确迹减少最大化器（使用完整的残差列，忽略数据/复杂度）。
  3. 第三层： $\Delta$-VFE（使用完整的残差列、数据向量和正则化逆来优化完整的 VFE）。

结果
在 Abalone 和 QM7 数据集上的数值实验表明：

• VFE 优化： 与贪婪法和 RPCholesky 相比，$\Delta$-VFE 始终能获得更紧的对数边际似然界（更小的相对 VFE 间隙），尤其是在低到中等秩（$r \le 1024$）的情况下。
• 近似质量： 该方法保持了与 RPCholesky 相当的迹范数近似质量。它并未为了提升 VFE 而牺牲标准的核近似精度。
• 预测性能： 在高斯过程回归任务中，改进的 VFE 转化为在低到中等秩下更低的预测误差（RMSE 和 MAE）。
• 批次大小敏感性： 增加批次大小 $s$ 会带来收益递减，但始终能改善 VFE 间隙和预测准确性。即使是较小的批次大小（例如 $s=8$ 或 $s=16$）也能比 RPCholesky 提供实质性的提升。

意义
本文声称，所提出的方法弥合了代数矩阵近似与特定任务推理目标之间的鸿沟。通过推导出 VFE 的精确闭式增益，作者提供了一种显式对齐于高斯过程概率推理目标的贪婪枢轴规则。研究结果表明，对于矩阵泛函包含数据拟合或复杂度项的应用场景，仅优化迹范数误差是不够的，面向目标的选择在不增加显著计算开销的情况下，能产生更优的实际表现。该方法被视为 RPCholesoles 的直接推广，它整合了关于目标函数的更多信息。