Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

技术摘要：基于向量场与后验认证的确定性零阶镜像下降法

1. 问题陈述
本文研究了在中等维度下进行确定性零阶（无导数）优化的挑战，特别适用于梯度不可用、计算成本过高或数值不稳定（例如涉及对数行列式的矩阵函数或量子相对熵）的目标函数。虽然标准的镜像下降（Mirror Descent, MD）通过 Bregman 散度提供了具备几何感知能力的优化方法，但它传统上依赖于精确梯度。现有的确定性无导数优化（DFO）方法（如直接搜索、信赖域模型）通常在欧几里得几何下运行，并侧重于平稳性度量，而非最后迭代值的函数值保证。相反，随机零阶方法提供了基于期望的界限，但缺乏在安全性关键或可审计应用中所需的复现性和单次运行的可验证性。核心问题在于开发一种确定性的零阶框架，该框架既能保留 Bregman 几何特性，又能仅利用函数值，并提供显式的、可验证的最后迭代收敛保证。

2. 方法论
作者提出了一个广义的 $\Omega$-驱动镜像下降 框架。该算法不再使用梯度 $\nabla f(x)$，而是采用由函数值确定性构造的通用向量场 $\Omega(x)$。

• 广义更新规则： 更新过程将原空间迭代点 $x_j$ 映射到对偶空间 $\theta_j = \nabla \Phi(x_j)$，执行步进 $\theta_{j+1} = \theta_j - \eta_j \Omega(x_j)$，然后映射回原空间 $x_{j+1} = (\nabla \Phi)^{-1}(\theta_{j+1})$。
• 后验认证： 分析依赖于轨迹向相对平滑条件（公式 2.5）：$\eta_j D_{f,\Omega}(x_{j+1} \| x_j) \leq D_\Phi(x_{j+1} \| x_j)$。与全局假设不同，该条件是沿着实际生成的迭代轨迹进行检查的。如果满足该条件，则可产生显式的最后迭代值保证。
• 穿孔邻域广义星凸性： 为了处理零阶预言机（oracle）固有的近似误差，本文引入了一种放宽的星凸性条件。它要求 $\langle \Omega(x), x - x^* \rangle \geq f(x) - f(x^*)$ 仅在极小值点 $x^*$ 的一个小邻域 $U$ 之外成立。这隔离了一个由零阶预言机分辨率决定的显式“误差底限（error floor）”。
• 确定性实例化： 该框架使用确定性中心有限差分法在适中维度下进行实例化。向量场 $\Omega(x)$ 通过 $2d$ 个偏离中心的函数求值（外加一个可重用的中心值）来构造。
• 鲁棒锥支配性： 本文的一个关键技术贡献是证明了有限差分向量场在特定集合 $V_{\epsilon, c}$ 之外满足所需的星凸性条件。这是通过将其建模为一个**鲁棒锥支配（robust conic dominance）**设计问题来实现的，确保一个经过缩放的代理方向能够支配所有可容许的真实方向，且这些方向位于一个圆锥不确定性范围内。

3. 核心贡献

• 统一框架： 本文建立了一个通用的 $\Omega$-驱动镜像下降模板，该模板涵盖了各种信息几何算法（包括广义 Blahut–Arimoto 更新）和确定性有限差分方案。
• 轨迹向认证： 它提供了一种单次运行、可验证证书的机制。如果沿特定轨迹满足相对平滑不等式，算法将保证特定的最后迭代值函数界限，且该界限独立于全局平滑假设。
• 显式误差底限分析： 对于确定性有限差分，作者推导出了一个“速率加底限”的收敛界限。在远离分辨率相关邻域之外，误差以 $O(1/t)$ 的速度衰减，且误差底限由有限差分步长 $\epsilon$ 和问题的条件数显式表征。
• 几何联系： 本研究揭示了连接 Bregman 级数恒等式、确定性认证以及零阶优化背景下的鲁棒锥几何（特别是二阶锥对偶）的隐藏几何结构。

4. 主要结果

• 定理 2.1 & 2.3： 在满足轨迹向相对平滑条件和穿孔邻域广义星凸性的条件下，算法保证：
  $$f(x_t) - f(x^*) \leq \max \left( \frac{D_\Phi(x^* \| x_1)}{\sum_{j=1}^{t-1} \eta_j}, \max_{x \in U} (f(x) - f(x^*)) \right)$$
  该界限将收敛速率（由 Bregman 散度和步长驱动）与近似误差（由邻域 $U$ 驱动）分离开来。
• 定理 6.4 & 推论 6.6： 当使用确定性中心有限差分实例化时，异常集 $V_{\epsilon, c}$ 被证明包含在一个半径与 $\epsilon\sqrt{d}$ 成比例的欧几里得球内。这产生了一个具体的界限，其中误差底限由该 $\epsilon$-邻域内的目标函数变化量决定。
• 可行性（定理 5.1）： 本文证明了对于足够小的步长，轨迹向相对平滑条件始终是可行的，从而证明了使用基于证书的线搜索的合理性。

5. 意义与主张
本文声称弥合了确定性零阶优化与几何感知镜像下降之间的鸿沟。其主要意义在于：

1. 确定性与可验证性： 提供了一个适用于需要复现性和可审计性应用（如科学计算、安全关键设计）的框架，在这些应用中，随机方法是不充分的。
2. 几何灵活性： 将 Bregman 几何（对于具有单纯形、熵或正定约束的问题至关重要）的优势扩展到梯度不可用的场景。
3. 理论洞察： 证明了对于零阶镜像下降，实现最后迭代保证的关键结构性假设并非经典的凸性，而是穿孔邻域广义星凸性。这一条件自然地容纳了有限差分近似的分辨率限制。
4. 方法论转向： 将重点从全局假设转向后验、轨迹向证书，允许从业者根据实际运行数据而非最坏情况理论界限来验证收敛保证。

作者将这项工作定位为现有 DFO 传统的补充，它提供了一个保留 Bregman 几何的特定接口，并提供了第一个针对仅基于函数值预言机的、可验证的最后迭代值（last-iterate）镜像下降式证书。