Power Homotopy for Zeroth-Order Non-Convex Optimizations

技术摘要：用于零阶非凸优化的幂次同伦法

问题陈述
本文解决了非凸问题中零阶（ZO）优化的挑战，即在无法获取梯度的情况下，必须最大化目标函数 $f: \mathbb{R}^d \to \mathbb{R}$。虽然现有的方法（如 GS-PowerOpt）利用幂变换高斯平滑来定位全局最优解，但它们依赖于固定的平滑半径 $\sigma$。作者指出了固定 $\sigma$ 设计中的一个根本局限性：全局探索与局部精细化之间的内在权衡。较大的 $\sigma$ 有助于全局探索并加速代理优化，但会扭曲代理极大值点的位置；相反，较小的 $\sigma$ 虽然能保留局部几何结构，但在迭代远离高值区域时，产生的梯度信号却非常微弱。

方法论：GS-PowerHP
为了解决这一权衡问题，作者提出了 GS-PowerHP（幂变换高斯同伦法），这是一种将幂变换与原则性的衰减平滑半径调度相结合的单圈零阶算法。

1. 目标变换： 该方法针对代理目标函数：
   $$F_{N,\sigma}(\mu) := \mathbb{E}_{x \sim \mathcal{N}(\mu, \sigma^2 I_d)}[e^{N f(x)}]$$
   其中 $N$ 是幂参数，$\sigma$ 是平滑半径。
2. 衰减调度： 与使用固定 $\sigma$ 的 GS-PowerOpt 不同，GS-PowerHP 在每次迭代 $t$ 时根据以下公式更新平滑半径：
   $$\sigma_{t+1} = \sigma_0 \beta^{t+1} + b$$
   其中 $\beta \in (0, 1)$ 是衰减因子，$b > 0$ 是下界。
3. 更新规则： 算法执行随机梯度上升步骤：
   $$\mu_{t+1} = \mu_t + \alpha_t \hat{\nabla} F_{N,\sigma_{t+1}}(\mu_t)$$
   梯度估计器是通过从 $\mathcal{N}(\mu_t, \sigma_{t+1}^2 I_d)$ 中抽取 $K$ 个样本计算得出的。
4. 机制： 该策略在开始阶段使用较大的 $\sigma$ 以在全局探索期间（当 $\mu_t$ 远离最优值时）保持有信息的梯度信号，并随着迭代逐渐减小 $\sigma$，以在迭代接近极大值点时提高局部精细化能力。

核心贡献

1. 理论洞察： 作者通过形式化分析，识别了 GS-PowerOpt 固定 $\sigma$ 机制中固有的探索与精细化权衡。他们证明了迭代复杂度与 $\sigma^2$ 成反比（倾向于较大的 $\sigma$），而代理极大值点与真实全局极大值点之间的对齐度随 $\sigma \to 0$ 而提高（倾向于较小的 $\sigma$）。
2. 算法创新： GS-PowerHP 是首个明确地将幂变换与增量式 $\sigma$ 衰减机制相结合的零阶方法。
3. 收敛保证： 本文建立了理论收敛结果（推论 1 和 3）。作者证明，在温和的假设下，GS-PowerHP 以期望意义收敛到全局极大值点的任意小的邻域内。其向一阶平稳点的有限时间收敛速率被证明为 $O((d^2 \epsilon^{-1} b^{-2})^{\frac{2}{1-2\gamma}})$，这验证了衰减调度既能实现快速的初始进展，又能确保极限状态下的局部精度。
4. 经验优越性： 大量实验表明，GS-PowerHP 在各种任务中始终优于固定 $\sigma$ 的基准方法（包括 GS-PowerOpt）以及其他基于平滑的 ZO 方法（如 ZOSGD、ZO-AdaMM 和 ZOSLGH）。

实验结果
作者在以下方面评估了 GS-PowerHP：

• 基准函数： 在 $d=100$ 维空间中最大化 Ackley 和 Rastrigin 函数。GS-PowerHP 在基于平滑的方法中取得了最高的适应度值，并且与 GS-PowerOpt 相比，所需的迭代次数更少。
• 对抗攻击（黑盒）： 该方法在针对 MNIST、CIFAR-10 和 ImageNet 分类器的“最可能”定向攻击中进行了测试。
  • 在 ImageNet ($d=150,528$) 上，GS-PowerHP 实现了 78% 的成功率，相比 GS-PowerOpt (47%) 和 ZOSLGHd (67%) 有了显著提升，同时保持了相当的扰动大小和图像相似度。
  • 在 MNIST 和 CIFAR-10 上，它以比竞争性的基于平滑的算法更小的扰动范数实现了 100% 的成功率。
• 消融研究： 在合成目标和定向攻击上的实验证实，衰减 $\sigma$ 机制是性能提升的主要驱动力，使算法能够比固定 $\sigma$ 变体更有效地平衡探索与精细化。

意义与主张
本文声称，GS-PowerHP 通过将平滑半径视为一种自适应计算资源而非静态超参数，代表了零阶非凸优化领域的重大进展。作者断言，这种方法解决了以往幂平滑方法中存在的结构性紧张关系。

该工作的意义在于其在极高维设置（如 ImageNet 攻击）下的鲁棒表现，在此类场景下，它不仅优于现有的基于平滑的方法，而且提供了比协方差自适应方法（如需要维护完整协方差矩阵的 CMA-ES）更轻量级的计算选择。作者总结道，幂变换与同伦式衰减的结合，既提供了强大的理论收敛保证，也为具有挑战性的黑盒优化任务提供了卓越的实证结果。