Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

以下是 Jonas Bresch 所著论文《二次函数商的零阶方法推广》的详细技术总结。

1. 问题陈述

本文旨在解决在零阶（无导数）约束下广义算子范数和极值广义瑞利商的优化问题。具体目标是求解：
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
其中 $A \in \mathbb{R}^{m \times d}$ 和 $B \in \mathbb{R}^{\ell \times d}$ 是仅可通过前向评估（黑盒访问）获取的矩阵。

关键约束与挑战：

• 无伴随/无矩阵： 伴随算子 $A^T$ 和 $B^T$ 不可用，或与正向算子不一致（常见于遗留代码、偏微分方程求解器和断层扫描中）。
• 适定性： $B$ 必须具有满列秩（$\text{rank}(B)=d$），以确保 $B^TB \succ 0$。
• 现有方法的局限性： 最近的先进零阶方法（例如 Bresch 等人 [7–9]）依赖于广义球面（$S^{d-1}_{B^TB}$）上的切空间采样。这需要已知度量 $B^TB$ 或其平方根以投影搜索方向，这在严格的黑盒设置中是不可行的。

2. 方法论

本文提出了一种根本不同的方法，基于在整个单位球面上的无约束采样，而非受限的切空间。

A. 无约束采样策略

该方法不再从广义球面的切空间（这需要 $B^TB$）中采样搜索方向 $x_k$，而是从标准单位球面 $S^{d-1}$ 上均匀采样 $x_k$：
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
这消除了对依赖度量的投影或伴随信息的需求。

B. 通过闭式解获得最优步长

对于当前迭代点 $v_k$ 和搜索方向 $x_k$，算法寻求最优步长 $\tau_k$ 以最大化沿收缩路径的目标函数。路径上的目标函数变为二次函数的商：
$$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$$
系数 ($a_k, \dots, f_k$) 仅使用 $A$ 和 $B$ 的前向评估计算得出。

• 理论突破： 本文证明，寻找最优 $\tau_k$ 等价于求解涉及 $2 \times 2$ Gram 矩阵 $M_k$ 和 $N_k$ 的二维广义特征值问题。
• 结果： 推导出了 $\tau_k$ 的闭式解（定理 3.1），确保步长针对特定随机方向是最优的，无需线搜索启发式方法。

C. 零阶黎曼优化框架

该方法仅利用函数值构建黎曼优化量的估计器：

1. 梯度估计器： 利用随机方向 $x_k$ 和最优步长逻辑，构建黎曼梯度的无偏估计器。
2. 海森矩阵估计器（拟牛顿）： 本文利用球面上均匀分布的四阶矩，推导出了黎曼海森矩阵的无偏估计器（推论 3.3）。这使得**零阶拟牛顿法（算法 3）**成为可能。
3. 方差缩减： 通过平均 $m$ 个独立样本（算法 2），降低了梯度估计器的方差，从而加速收敛。

3. 主要贡献

1. $S^{d-1}$ 上的无约束采样：
   本文引入了一种采样方案，该方案在整个单位球面上运行，而非广义球面的切空间。这消除了对 $B^TB$ 或其伴随算子的要求，使该方法适用于先前方法失败的严格黑盒场景。

2. 闭式最优步长：
   与使用固定或启发式步长的标准零阶方法不同，这项工作针对特定的二次商目标函数推导出了最优步长 $\tau_k$ 的精确闭式解。这将子问题转化为可解的二维广义特征值问题。

3. 无偏海森矩阵估计：
   作者提供了在无导数设置下黎曼海森矩阵无偏估计器的原理性推导。这使得构建能够捕捉曲率信息而无需显式导数的二阶零阶算法（拟牛顿法）成为可能。

4. 理论收敛保证：

   • 几乎必然收敛： 迭代序列几乎必然收敛到主广义特征子空间（定理 3.7）。
   • 临界点分析： 本文证明了梯度代理序列 ($\alpha_k$) 几乎必然收敛于零，确保算法不会陷入非最优临界点（在温和的谱假设下）。
   • 良定性： 证明了步长计算中的分母几乎必然保持非零，确保算法是良定义的。

4. 数值结果

实验在维度高达 $d=1000$ 的合成随机高斯矩阵上进行。

• 与最先进方法的性能对比：
  • 在低维情况下，所提出的方法与最近的切空间采样方法 [9] 相当。
  • 在高维情况下（$d \gg 10$），无约束球面采样显著优于切空间方法。这归因于更大的搜索空间以及避免了切空间方法所需的昂贵投影操作（矩阵 - 矩阵乘法）。
• 收敛速率：
  • 该方法对相对商误差（RQE）表现出线性收敛。
  • 广义特征方程的最小平方残差（MSQR）显示出 $O(1/k)$ 的收敛速率，优于无导数方法中常见的次线性速率。
• 二阶优势：
  拟牛顿变体（算法 3）在临界点附近表现出比一阶变体（算法 2）更严格的收敛行为和更快的误差减少，有效地缩小了在最优解附近的性能差距。

5. 意义

这项工作代表了谱问题无导数优化领域的重大进步。

• 实际影响： 它使得在伴随算子不可用、不一致或计算成本过高（例如遗留仿真代码、复杂偏微分方程求解器）的场景中，能够计算算子范数和瑞利商。
• 理论影响： 它通过提供流形上梯度和海森矩阵的无偏估计器（无需显式流形投影），弥合了零阶随机搜索与黎曼优化之间的差距。
• 算法效率： 闭式步长以及无需切空间投影即可运行的能力，使得该算法具有计算高效性，并可扩展到高维问题。

总之，Bresch 通过将受限的切空间采样替换为无约束的球面采样、推导精确步长以及建立严格的二阶框架，将零阶方法推广到处理二次函数的商，从而在高维黑盒设置中超越了现有的最先进技术。