技术摘要：通过具有确定性积分时间的哈密顿动力学实现加速凸优化

问题陈述

本文研究的是一阶凸优化问题，即在给定梯度算子 $\nabla f$ 的情况下，最小化一个可微凸函数 $f: \mathbb{R}^d \to \mathbb{R}$。作者致力于为平滑凸目标函数和 $\alpha$-强凸目标函数实现加速收敛速率。

虽然经典的梯度下降法对于凸函数实现 $O(1/\epsilon)$ 的收敛速率，对于强凸函数实现 $O(\log(1/\epsilon))$ 的收敛速率，而 Nesterov 加速梯度法将这些速率分别提升至 $O(1/\sqrt{\epsilon})$ 和 $O(\sqrt{\kappa}\log(1/\epsilon))$。最近的研究尝试通过连续时间动力系统（通常利用二阶微分方程）来推导这些速率。然而，现有的基于哈密顿动力学的优化方法存在局限性：

1. 它们通常要求目标函数为二次函数。
2. 当应用于一般凸函数时，先前的保证（例如 Fu 和 Wibisono, 2025）是随机性的，仅在对随机积分时间求期望的情况下成立。
3. 它们通常依赖于轨迹的终点，这导致在没有特定结构假设的情况下，无法为一般凸函数提供加速。

其目标是开发一种确定性的、基于哈密顿动力学的算法，能够在不依赖随机化或二次项假设的情况下，为一般的平滑凸和强凸函数实现最优的一阶复杂度。

方法论

所提出的方法利用了哈密顿流 (Hamiltonian Flow, HF)，但引入了一种关于如何利用该轨迹进行优化的新颖视角。

1. 哈密顿动力学框架

作者在相空间 $\mathbb{R}^{2d}$（位置 $X_t$ 和速度 $Y_t$）上定义了一个具有能量函数 $H(x, y) = f(x) + \frac{1}{2}\|y\|^2$ 的哈密顿系统：
$$\dot{X}_t = Y_t, \quad \dot{Y}_t = -\nabla f(X_t)$$
该系统的一个关键特性是能量守恒：$f(X_t) + \frac{1}{2}\|Y_t\|^2 = f(X_0) + \frac{1}{2}\|Y_0\|^2$。如果以 $Y_0=0$ 初始化，则函数值 $f(X_t)$ 永远不会超过 $f(X_0)$。

2. 核心洞察：平均值 vs. 终点

本文的核心理论贡献在于观察到：对于凸函数 $f$，哈密顿轨迹上的时间平均位置比轨迹的终点能提供更强的下降保证。

• 引理 2 建立了一个微分不等式，表明轨迹的平均值可以收缩最优性间隙（optimality gap）。
• 推论 1 证明了通过特定加权平均得到的轨迹位置 $X_{\text{avg}}(X_0; T) = \frac{2}{T^2} \int_0^T (T-t)X_t dt$ 满足收缩性质：
  $$f(X_{\text{avg}}) - f(z) + \frac{1}{3T^2}\|X_T - z\|^2 \leq \frac{2}{3}(f(X_0) - f(z)) + \frac{1}{3T^2}\|X_0 - z\|^2$$
  这表明，只要选择合适的积分时间 $T$，最优性间隙就具有通用的 $2/3$ 收缩因子。

3. 算法设计

基于这一洞察，本文提出了两种算法：

• HFA (用于优化的哈密顿流平均法)： 一种理想化的连续时间算法。它迭代地将当前迭代点提升到相空间，模拟精确的哈密顿流时长 $T_k$，计算轨迹的加权平均值，并可选地将此平均值与终点混合，以形成下一个迭代点。

  • 对于强凸函数，算法仅使用加权平均值（$\lambda=0$）。
  • 对于凸函数，它使用平均值与终点的混合（$\lambda=1$）来处理缺乏二次增长性的问题。

• dHFA-eg (带有外梯度法的离散化 HFA)： 一个实际的离散时间实现。由于精确模拟 HF 通常是不可能的，作者使用外梯度积分器 (extragradient integrator) 对流进行离散化（这是一种近似隐式积分器的一阶方法）。

  • 连续积分被替换为离散加权和。
  • 算法保持相同的结构：模拟 $N_k$ 步，计算离散加权平均值，并与最终迭代点进行混合。

核心贡献

1. 通过平均化实现确定性加速： 本文证明了基于哈密顿动力学的方法可以为一般的平滑凸和强凸函数确定性地实现加速收敛速率。这与之前的工作（Fu 和 Wibisono, 2025）形成对比，后者需要随机化积分时间才能在期望意义下达到类似速率。
2. 新型收缩引理： 作者推导了引理 2 和推论 1，这些引理形式化了哈密顿轨迹的时间平均值以 $2/3$ 的因子收缩最优性间隙（外加残差项）这一事实。这一性质此前并未在一般凸目标函数上得到确立。
3. 最优复杂度： 提出的离散算法 dHFA-eg 达到了与 Nesterov 加速梯度法相同的迭代复杂度：
   • 强凸情况： $O(\sqrt{\kappa} \log(1/\epsilon))$ 次梯度计算。
   • 凸情况： $O(\sqrt{L/\epsilon})$ 次梯度计算。
     其中 $\kappa = L/\alpha$ 是条件数。
4. 实用的离散化： 该工作通过利用外梯度积分器，弥合了连续时间动力系统与可实现的梯度算法之间的鸿沟，该积分器仅需要梯度访问（无需近端算子/proximal oracle）。

结果

论文为所提出的算法提供了严格的理论保证：

• 强凸情况： 对于满足 $\alpha$-二次增长（由 $\alpha$-强凸性隐含）的函数，运行 HFA（或 dHFA-eg）且积分时间 $T \propto 1/\sqrt{\alpha}$，可获得几何收敛速率。定理 1 和定理 3 表明误差以 $(2/3 + \delta)^K$ 的速度衰减，从而实现最优的 $O(\sqrt{\kappa} \log(1/\epsilon))$ 复杂度。
• 凸情况： 对于一般的凸函数，算法需要几何级数地增加积分时间 $T_k$（或离散化步数 $N_k$）。定理 2 和定理 4 表明，尽管每步迭代的成本在增加，但在达到 $\epsilon$-精度所需的总复杂度仍为 $O(1/\sqrt{\epsilon})$。
• 确定性保证： 所有的收敛界限都对算法的每一次执行都成立，而不仅仅是在期望意义下。

意义与主张

作者声称，这项工作确立了哈密顿动力学作为确定性加速凸优化的一种有效的算法原语。

• 范式转移： 这项工作实现了视角的转变——从“通过采样进行优化”（利用优化思想改进采样）到“通过采样思想进行优化”（利用哈密顿流概念改进优化）。
• 鲁棒性： 不同于以往受限于二次目标函数或需要随机化的哈密顿优化方法，这种方法可以处理一般的平滑凸函数并提供确定性保证。
• 理论基础： 论文提供了一个新的微分不等式（引理 2），解释了为什么对轨迹进行平均化是有效的，从而为理解连续时间动力学与离散加速方法之间的关系提供了更深的理解。

作者指出，虽然其分析侧重于凸函数，但这些技术可能对非凸优化和加速采样（HMC）产生影响，不过这些属于未来的研究方向。本文并不声称在渐近复杂度上超越 Nesterov 方法，而是旨在提供另一种能够确定性达到相同最优速率的、基于动力学的推导方式。