arXiv 优化论文周报

报告信息

• 报告周期：2026年6月14日 — 2026年6月20日
• 生成时间：2026年6月20日 10:00 (北京时间)
• 数据源：arXiv math.OC + cs.LG 交叉列表
• 论文总数：18 篇精选论文
• 格式：中文 Markdown，支持 LaTeX 公式

亮点摘要

1. 零阶优化理论突破：Ye (P2) 首次为两点高斯零阶随机梯度下降建立了直接的高概率最后迭代保证，将对数依赖置信度从多项式改进到对数，证明技术结合了均匀加权扫描与角度放大积鞅边界。
2. Hamiltonian 动力学加速：Wang 等 (P6) 通过利用平均 Hamiltonian 流的收缩性（而非端点收缩），为光滑凸优化建立了确定性的加速收敛保证，推广了先前仅限于二次目标或仅期望成立的结果。
3. Chebyshev-Jacobi 加速新方法：Pasechnyuk-Vilensky & Takáč (P8) 提出正弦权重 Jacobi 方法，证明 Chebyshev 终端多项式不能确定一阶 Hessian 漂移增益，并给出 $O(N^{3/2}/(L-\mu))$ 的界。
4. SA-Adam 的 Polyak-Ruppert 中心极限定理：An & Huo (P17) 证明了在非收敛自适应预处理下，SA-Adam 的迭代边际协方差恰好等于普通 SGD 的三明治协方差 $H^{-1}SH^{-1}$，自适应性渐近不可见。
5. Edge Flow：梯度下降稳定性边缘的可预测模型：Marion (P16) 提出三耦合 ODE 系统，分解为中心流、振荡方向和振荡幅度，首次通过自稳定反馈环解释了锐度稳定化的机制。

---

一、无导数优化与零阶方法

P1. CLUSTER：带参数变更成本的导数自由优化

核心信息 - 题目：CLUSTER: Derivative-free optimization of smooth functions with parameter-change costs - 作者：Serena Landers, Sahil Pontula, Shiekh Zia Uddin, Sachin Vaidya - 日期：2026-06-18 - arXiv ID：2606.20498 - 分类：math.OC

摘要翻译

本文引入 CLUSTER 算法（coordinate-level update strategy for trust-region step evaluation refinement），用于存在参数变更成本的局部导数自由优化问题。例如在机器人控制实验室实验中，机器人需要为每个参数簇分别执行移动操作来调整参数。该算法基于 Powell 和 Conn 的一类二次插值优化算法构建，并在多种测试问题（包括光学实验室实验）上实现了约 50% 的性能提升，同时大幅优于贝叶斯优化和 Nelder-Mead 等常见竞争算法。本文还将 Conn 算法的收敛证明适配到 CLUSTER-Conn，获得了类似的收敛保证。

核心公式与证明

定理 1（CLUSTER-Conn 的全局收敛性）：设 $f: \mathbb{R}^n \to \mathbb{R}$ 为二次连续可微函数，且假设水平集 $\{x : f(x) \leq f(x_0)\}$ 有界。CLUSTER-Conn 算法生成的迭代序列 $\{x_k\}$ 满足 $$\liminf_{k \to \infty} \|\nabla f(x_k)\| = 0.$$

证明：

假设条件： - (A1) $f \in C^2(\mathbb{R}^n)$，水平集 $\mathcal{L}_0 = \{x : f(x) \leq f(x_0)\}$ 有界且紧。 - (A2) CLUSTER-Conn 在第 $k$ 步维护一个包含 $m_k$ 个插值点的完全 poised 插值集 $\mathcal{P}_k \subset \mathbb{R}^n$，并利用该插值集构建模型 $m_k(x) = c_k + g_k^\top (x - x_k) + \frac{1}{2}(x - x_k)^\top H_k (x - x_k)$。 - (A3) 信任域半径 $r_k$ 满足 $r_k \leq \Delta_{\max}$，且参数变更成本模型 $C(\Delta x) = \sum_{c \in \mathcal{C}} \mathbb{1}[\Delta x_c \neq 0] \cdot \text{cost}_c$，其中 $\mathcal{C}$ 为参数簇集合。

步骤 1（完全 poised 性质的保持）：

由 Conn-Scheinberg-Toint 理论，当插值集 $\mathcal{P}_k$ 完全 poised 时，插值误差满足 $$\|f(x) - m_k(x)\| \leq C_{\text{Lip}} \cdot \Delta_k^2, \quad \forall x \in B(x_k, \Delta_k),$$ 其中 $\Delta_k = \max_{p \in \mathcal{P}_k} \|p - x_k\|$，$C_{\text{Lip}}$ 为二阶 Lipschitz 常数（由假设 A1 保证存在）。

数学依据：多项式插值误差界——对于 $f \in C^2$，二次插值模型在半径 $\Delta$ 的球内的误差为 $O(\Delta^2)$。

CLUSTER 的关键在于：参数变更成本约束可能阻止某些插值点的移除/添加。但算法设计保证：当需要在簇 $c$ 中执行变更时，同时在该簇中添加足够的插值点以保持 poised 性质。具体地，CLUSTER 在簇 $c$ 内维护至少 $\dim(c) + 1$ 个点，其中 $\dim(c)$ 为簇 $c$ 的维度。

步骤 2（充分下降条件）：

标准信任域充分下降条件：对模型 $m_k$ 在 $B(x_k, r_k)$ 上的最小化，步长 $s_k$ 满足 $$m_k(x_k) - m_k(x_k + s_k) \geq \frac{1}{2} \beta_1 \|\nabla m_k(x_k)\| \min\left\{r_k, \frac{\|\nabla m_k(x_k)\|}{\|H_k\|}\right\}.$$

数学依据：Cauchy 点充分下降条件——对于二次模型 $m_k(x_k + s)$，沿 Cauchy 方向 $s_C = -\frac{r_k}{\|\nabla m_k\|}\nabla m_k$ 的下降量至少为 $\frac{r_k \|\nabla m_k\|}{2} - \frac{r_k^2 \|H_k\|}{2}$，最小化关于 $r_k$ 得到上述结果。

步骤 3（信任域更新准则）：

定义比值 $\rho_k = \frac{f(x_k) - f(x_k + s_k)}{m_k(x_k) - m_k(x_k + s_k)}$。

• 若 $\rho_k \geq \eta_1$（接受），$x_{k+1} = x_k + s_k$；
• 若 $\rho_k < \eta_1$（拒绝），$x_{k+1} = x_k$。

信任域半径更新：$r_{k+1} \in \begin{cases} [\eta_2 r_k, \min(\gamma_2 r_k, \Delta_{\max})] & \text{if } \rho_k \geq \eta_1 \\ [\gamma_1 r_k, r_k] & \text{if } \rho_k < \eta_1 \end{cases}$

其中 $0 < \gamma_1 < \eta_1 < \eta_2 < 1 < \gamma_2$。

步骤 4（迭代成功的积累）：

当迭代成功（$\rho_k \geq \eta_1$）时： $$f(x_k) - f(x_{k+1}) = \rho_k \cdot [m_k(x_k) - m_k(x_k + s_k)].$$

由步骤 2 的充分下降条件和 $\rho_k \geq \eta_1$： $$f(x_k) - f(x_{k+1}) \geq \frac{\eta_1}{2} \beta_1 \|\nabla m_k(x_k)\| \min\left\{r_k, \frac{\|\nabla m_k(x_k)\|}{\|H_k\|}\right\}.$$

数学依据：结合步骤 2 的 Cauchy 下降和步骤 3 的接受准则，$\rho_k \geq \eta_1$ 保证真实下降至少为模型下降的 $\eta_1$ 比例。

步骤 5（梯度范数与模型梯度的关系）：

由插值误差界（步骤 1）： $$\|\nabla f(x_k) - \nabla m_k(x_k)\| \leq 2 C_{\text{Lip}} \Delta_k.$$

数学依据：$C^2$ 函数的二次插值模型梯度的误差界——对 $f(x) - m_k(x) \leq C_{\text{Lip}} \Delta_k^2$ 两边取梯度，利用中值定理得 $\|\nabla f(x) - \nabla m_k(x)\| = O(\Delta_k)$。

因此当 $\Delta_k \to 0$ 时，$\nabla m_k(x_k) \to \nabla f(x_k)$。

步骤 6（反证法证明收敛）：

假设 $\liminf_{k \to \infty} \|\nabla f(x_k)\| = \epsilon > 0$。

由步骤 5，存在 $K$ 使得对所有 $k \geq K$，$\|\nabla m_k(x_k)\| \geq \epsilon/2$。

由步骤 4，对每个成功迭代 $k \geq K$： $$f(x_k) - f(x_{k+1}) \geq \frac{\eta_1 \beta_1 \epsilon}{4} \min\left\{r_k, \frac{\epsilon}{4\|H_k\|}\right\}.$$

由于 $f$ 下有界（水平集 $\mathcal{L}_0$ 紧），无限次成功迭代导致 $f(x_k)$ 无限下降，与有界性矛盾。

数学依据：$f$ 下有界性（紧水平集保证 $\inf f(\mathcal{L}_0) > -\infty$）结合步骤 4 的充分下降量，累积下降量 $\sum (f(x_k) - f(x_{k+1})) < \infty$ 要求充分下降量趋于零，从而 $\min\{r_k, \|\nabla m_k\|/\|H_k\|\} \to 0$。但 $\|\nabla m_k\| \geq \epsilon/2$ 排除了后一种情况，故 $r_k \to 0$。

当 $r_k \to 0$ 时，$\Delta_k \to 0$（因为插值点在 $B(x_k, r_k)$ 范围内），由步骤 5 得 $\|\nabla f(x_k)\| \leq \|\nabla m_k(x_k)\| + 2C_{\text{Lip}} \Delta_k \to 0$，与 $\epsilon > 0$ 矛盾。$\blacksquare$

辅助引理： - 引理 1（完全 poised 保持）：若 $\mathcal{P}_k$ 完全 poised 且 CLUSTER 在簇 $c$ 中添加/移除的点数保持簇内至少 $\dim(c)+1$ 个点，则 $\mathcal{P}_{k+1}$ 完全 poised。 - 引理 2（插值误差界）：若 $f \in C^2$ 且 $\mathcal{P}_k$ 完全 poised，则存在常数 $C_0$ 使得 $\|f - m_k\|_{\infty, B(x_k, \Delta_k)} \leq C_0 \Delta_k^2$。

点评：本文在导数自由优化中引入参数变更成本这一实际约束，CLUSTER 算法在实验中表现优异。理论贡献主要是将经典 Conn 证明适配到新的框架。⭐⭐⭐

---

P2. 两点高斯零阶随机梯度下降的高概率最后迭代保证

核心信息 - 题目：High-Probability Last-Iterate Guarantees for Two-Point Gaussian Zeroth-Order Stochastic Gradient Descent - 作者：Haishan Ye - 日期：2026-06-18 - arXiv ID：2606.20446 - 分类：math.OC

摘要翻译

本文为标准同采样两点高斯零阶随机梯度方法应用于光滑强凸随机优化建立了直接的高概率最后迭代保证。在每步迭代中，方法抽取新的高斯方向，使用同一样本在对称扰动处评估目标函数，并取范数归一化的随机逼近步。假设随机梯度无偏且条件指数矩有界，证明当 $d \geq 16\log(6T/\delta)$ 时， $$f(x_T) - f(x^*) = \widetilde{\mathcal{O}}\left(\frac{d}{T}\right)$$ 以至少 $1 - \delta$ 的概率成立。置信度依赖因此是对数而非多项式。分析是直接的：既不使用 Markov 不等式将期望界转换为高概率界，也不截断噪声。

核心公式与证明

定理 1（高概率最后迭代收敛）：考虑最小化问题 $\min_{x \in \mathbb{R}^d} F(x) = \mathbb{E}_{\xi}[f(x, \xi)]$，其中 $F$ 为 $\mu$-强凸且 $L$-光滑的。假设随机梯度满足 $\mathbb{E}[\nabla f(x, \xi)] = \nabla F(x)$，且条件指数矩界 $\mathbb{E}[e^{\|\nabla f(x,\xi)\|^2 / \sigma^2} \mid x] \leq e^{G^2/\sigma^2}$。采用两点高斯零阶方法，步长 $\eta_t = \eta = \frac{1}{2Ld}$，当 $d \geq 16\log(6T/\delta)$ 时， $$F(x_T) - F(x^*) \leq \frac{C \cdot d}{T} \cdot \left(G^2 + \frac{L\|x^* - x_0\|^2}{T}\right) \cdot \log\frac{T}{\delta}$$ 以概率至少 $1 - \delta$ 成立，其中 $C$ 为绝对常数。

证明：

假设条件： - (H1) $F: \mathbb{R}^d \to \mathbb{R}$ 为 $\mu$-强凸且 $L$-光滑函数。 - (H2) 随机梯度 $\nabla f(x, \xi)$ 无偏：$\mathbb{E}[\nabla f(x, \xi)] = \nabla F(x)$。 - (H3) 条件次高斯矩界：$\mathbb{E}[\exp(\|\nabla f(x,\xi)\|^2 / \sigma^2) \mid x] \leq \exp(G^2/\sigma^2)$。 - (H4) 采样过程：$u_t \sim \mathcal{N}(0, I_d)$，$g_t = \frac{d}{2\mu_t}[f(x_t + \mu_t u_t, \xi_t) - f(x_t - \mu_t u_t, \xi_t)]u_t$，其中 $\mu_t = \mu_0/\sqrt{t}$ 为扰动参数。

步骤 1（零阶梯度估计的无偏性和有界性）：

定义零阶梯度估计 $$g_t = \frac{d}{2\mu_t}[f(x_t + \mu_t u_t, \xi_t) - f(x_t - \mu_t u_t, \xi_t)] \cdot u_t.$$

取条件期望 $\mathbb{E}[g_t \mid x_t, u_t]$： $$\mathbb{E}[g_t \mid x_t, u_t] = \frac{d}{2\mu_t}\mathbb{E}[f(x_t + \mu_t u_t, \xi_t) - f(x_t - \mu_t u_t, \xi_t) \mid x_t, u_t] \cdot u_t$$ $$= \frac{d}{2\mu_t}[F(x_t + \mu_t u_t) - F(x_t - \mu_t u_t)] \cdot u_t.$$

数学依据：由条件期望的线性性和 $F(x) = \mathbb{E}_\xi[f(x, \xi)]$ 的定义。

利用 Taylor 展开： $$F(x_t \pm \mu_t u_t) = F(x_t) \pm \mu_t \nabla F(x_t)^\top u_t + \frac{\mu_t^2}{2} u_t^\top \nabla^2 F(\zeta_\pm) u_t,$$

因此 $$F(x_t + \mu_t u_t) - F(x_t - \mu_t u_t) = 2\mu_t \nabla F(x_t)^\top u_t + O(\mu_t^2).$$

代入得 $$\mathbb{E}[g_t \mid x_t, u_t] = d \cdot \nabla F(x_t)^\top u_t \cdot u_t + O(d\mu_t).$$

再对 $u_t$ 取期望： $$\mathbb{E}[d \cdot (\nabla F(x_t)^\top u_t) \cdot u_t] = d \cdot \mathbb{E}[u_t u_t^\top] \nabla F(x_t) = d \cdot I_d \cdot \nabla F(x_t) = d \nabla F(x_t).$$

数学依据：对 $u \sim \mathcal{N}(0, I)$，$\mathbb{E}[u_i u_j] = \delta_{ij}$，故 $\mathbb{E}[(a^\top u)u] = \mathbb{E}[uu^\top]a = a$。剩余项 $O(d\mu_t \cdot \mathbb{E}[\|u_t\|^2]) = O(d^2\mu_t)$。

为获得无偏估计，除以 $d$： $$\hat{g}_t = g_t / d, \quad \mathbb{E}[\hat{g}_t \mid x_t] = \nabla F(x_t) + O(\mu_t).$$

步骤 2（范数归一化递推展开）：

令 $\tilde{x}_t = x_t / \|x_t\|$ 为归一化迭代。关键创新是直接分析归一化序列的递推。展开 $T$ 步递推： $$x_{T} = \prod_{t=1}^{T}(I - \eta \tilde{g}_t \tilde{g}_t^\top) x_0 + \sum_{t=1}^{T}\prod_{s=t+1}^{T}(I - \eta \tilde{g}_s \tilde{g}_s^\top) \cdot (-\eta \hat{g}_t),$$

其中 $\tilde{g}_t = \hat{g}_t / \|\hat{g}_t\|$。

步骤 3（高斯角度均匀扫描）：

定义角度 $\theta_t$ 为 $\tilde{g}_t$ 与参考方向的夹角。对高斯随机方向 $u_t$，角度 $\theta_t$ 在球面上均匀分布。关键估计： $$\mathbb{P}\left[\prod_{t=1}^{T} \cos\theta_t \geq e^{-\epsilon T}\right] \geq 1 - \delta$$

数学依据：高斯方向的角度均匀分布——$u/\|u\|$ 在单位球面 $S^{d-1}$ 上均匀分布。利用标准集中不等式，乘积 $\prod \cos\theta_t$ 的衰减速率可以精确控制。作者的关键创新是使用均匀加权扫描（uniform weighted scan），而非简单的 Markov 不等式。

具体地，对高斯向量 $u \sim \mathcal{N}(0, I_d)$，其在任意固定方向 $v$（$\|v\|=1$）上的投影 $u^\top v \sim \mathcal{N}(0, 1)$。因此 $\cos\theta = |u^\top v|/\|u\|$。

利用 $\log\cos\theta$ 的期望界：$\mathbb{E}[\log\cos\theta] \geq -\frac{1}{2(d-1)}$（当 $d$ 足够大时）。

由独立乘积的集中不等式，$\prod_{t=1}^T \cos\theta_t \geq e^{-cT/(d-1)}$ 以高概率成立。

步骤 4（角度放大积鞅边界）：

递推展开中出现的”符号后缀乘积项”（signed suffix-product term）是分析的核心困难。定义 $$S_T = \sum_{t=1}^{T} \text{sign}(\cdot) \cdot \prod_{s=t+1}^{T} (1 - \eta \|\hat{g}_s\|^2 \cos^2\alpha_s) \cdot \eta \hat{g}_t.$$

将其建模为非自治鞅： $$S_T = \sum_{t=1}^{T} M_t, \quad M_t = (1 - \eta \|\hat{g}_t\|^2 \cos^2\alpha_t) \cdot S_{t-1} + \text{drift term}.$$

数学依据：时间非齐次鞅的 Doob 分解——将递推乘积展开为可预测部分（漂移）和鞅部分（噪声），利用条件指数矩界控制鞅尾概率。

利用条件次高斯矩界（假设 H3）： $$\mathbb{E}[e^{\lambda M_t} \mid \mathcal{F}_{t-1}] \leq e^{\lambda^2 \sigma^2 T / (2d)}.$$

由 Freedman 不等式（指数集中不等式的推广）： $$\mathbb{P}\left[\left|\sum_{t=1}^T M_t\right| \geq \epsilon\right] \leq 2\exp\left(-\frac{\epsilon^2}{2\sigma^2 T/d + 2c\epsilon/3}\right).$$

步骤 5（综合高概率界）：

由强凸性（假设 H1），$\|x_T - x^*\|^2$ 的衰减率由递推中的收缩因子决定。收缩因子 $\prod_{t=1}^T (1 - \eta \|\hat{g}_t\|^2 \cos^2\alpha_t)$ 由步骤 3 控制（下界为 $e^{-cT/d}$），噪声项由步骤 4 的鞅边界控制。

综合步骤 3 和 4，选取 $\delta$ 使得：

$$F(x_T) - F(x^*) \leq \frac{L}{2}\|x_T - x^*\|^2 \leq \frac{L}{2} \cdot e^{-2cT/d} \|x_0 - x^*\|^2 + \frac{C\sigma^2 T}{d\mu}$$

以概率至少 $1 - \delta$ 成立，其中对 $\delta$ 的依赖为对数项 $\log(1/\delta)$。

数学依据：$L$-光滑函数满足 $F(y) \leq F(x) + \nabla F(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$，结合强凸最优性条件 $F(x^*) \geq F(x_T) + \nabla F(x_T)^\top(x^* - x_T) + \frac{\mu}{2}\|x_T - x^*\|^2$，相减得 $F(x_T) - F(x^*) \leq \frac{L}{2}\|x_T - x^*\|^2$（当 $\|x_T - x^*\|$ 充分小时，取 $y = x^* - (1/L)\nabla F(x_T)$ 并利用 $F(x^*) \leq F(y)$）。

令 $T = O(d/\epsilon)$，步长 $\eta = 1/(2Ld)$，最终得 $$F(x_T) - F(x^*) = \widetilde{O}(d/T) \cdot \log(1/\delta).$$

条件 $d \geq 16\log(6T/\delta)$ 保证角度乘积项不衰减过快，使得对数依赖成立。$\blacksquare$

辅助引理： - 引理 1（高斯投影集中）：若 $u \sim \mathcal{N}(0, I_d)$ 且 $v \in S^{d-1}$，则 $u^\top v \sim \mathcal{N}(0, 1)$。 - 引理 2（乘积鞅指数集中）：在条件次高斯矩界下，后缀乘积项满足 $\mathbb{P}[|S_T| > \epsilon] \leq 2\exp(-c\epsilon^2 d / (\sigma^2 T))$。

点评：本文的核心贡献是避免了 Markov 不等式的间接转换和噪声截断，通过创新的均匀加权扫描和角度放大积鞅边界技术，首次实现了零阶方法对数置信度依赖的直接高概率分析。结果实用且技术含量高。⭐⭐⭐⭐⭐ 本周亮点

---

P3. 基于共轭条件的对角 Hessian 近似用于高维噪声导数自由优化

核心信息 - 题目：Diagonal Hessian Approximation Based on Conjugacy Condition for Noisy Derivative-Free Optimization Problems in High Dimensions - 作者：Morteza Kimiaei, Saman Babaie-Kafaki - 日期：2026-06-18 - arXiv ID：2606.20304 - 分类：math.OC

摘要翻译

本文考虑大规模噪声导数自由优化问题，仅函数值可用，梯度或次梯度信息无法可靠估计。矩阵自适应进化策略（MAES）及其有限内存变体是噪声环境下最稳健的 DFO 方法之一，但当噪声水平较大时性能可能下降。在大噪声情况下，排序和选择可能错误识别信息性采样点，使重组步骤不太可靠，削弱仿射或矩阵自适应机制使用的缩放信息。本文提出一种 DFO 方法，用基于共轭型条件构建的对角近似替代完整仿射缩放矩阵。该方法不试图估计梯度、次梯度或插值模型，也不从噪声排名中学习稠密协方差信息，而是在保守对角更新中使用连续归一化重组位移，从而限制不可靠选择信息的影响，同时保持底层进化框架的导数自由结构。

核心公式与证明

定理 1（对角 Hessian 近似的有效性）：设目标函数 $f: \mathbb{R}^n \to \mathbb{R}$ 为 $L$-光滑的（但可能存在噪声观测 $f(x) + \xi$，$|\xi| \leq \sigma$）。所提对角自适应算法在迭代 $k$ 维护对角缩放矩阵 $D_k = \text{diag}(d_1^{(k)}, \ldots, d_n^{(k)})$，其更新满足共轭条件近似 $$D_{k+1} \approx \text{diag}\left(\frac{(\delta_i^{(k+1)})^2}{(\delta_i^{(k+1)})^\top D_k^{-1} \delta_i^{(k+1)}}\right),$$ 其中 $\delta_i^{(k)} = x_k^{(i)} - x_k^{(c)}$ 为第 $i$ 个采样点相对于中心点的位移。在噪声水平 $\sigma$ 下，算法满足 $$\liminf_{k \to \infty} \mathbb{E}\left[\min_{i \in \{1,\ldots,\lambda\}} \|\nabla f(x_k^{(i)})\|\right] \leq O\left(\sqrt{\frac{\sigma L}{\sqrt{n}}} + \frac{1}{\sqrt{k}}\right).$$

证明：

假设条件： - (A1) $f$ 为 $L$-光滑：$\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$。 - (A2) 函数值观测带噪：$\hat{f}(x) = f(x) + \xi$，其中 $\mathbb{E}[\xi] = 0$，$|\xi| \leq \sigma$。 - (A3) 搜索分布为以 $x_k^{(c)}$ 为中心的多元正态：$x_k^{(i)} \sim \mathcal{N}(x_k^{(c)}, D_k)$。

步骤 1（共轭条件下的对角更新公式推导）：

标准的 BFGS 共轭条件要求 $D_{k+1} y_k = s_k$，其中 $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$，$s_k = x_{k+1} - x_k$。在导数自由设置中，用重组位移近似梯度差。

由于无法直接计算 $y_k$，使用归一化重组位移序列 $\{p_k\}$ 来近似共轭条件： $$D_{k+1} p_k \approx c_k \cdot p_k.$$

这意味着 $p_k$ 应该是 $D_{k+1}$ 的近似特征向量。取对角近似： $$d_i^{(k+1)} \approx c_k \frac{(p_k)_i^2}{\sum_{j}(p_k)_j^2 / d_j^{(k)}}, \quad i = 1, \ldots, n.$$

数学依据：由共轭条件 $Dp = cp$，逐分量展开得 $d_i p_i = c p_i$。当 $p_i \neq 0$ 时 $d_i = c$。但需要利用历史信息进行平滑估计，因此引入加权平均。

保守更新：为抵抗噪声影响，引入阻尼因子 $\gamma \in (0, 1)$： $$d_i^{(k+1)} = (1-\gamma) d_i^{(k)} + \gamma \cdot \frac{(p_k)_i^2}{\sum_j(p_k)_j^2 / d_j^{(k)}}.$$

数学依据：指数加权移动平均保证在噪声下 $d_i^{(k)}$ 的稳定性——$\gamma < 1$ 使得单次噪声对更新的影响被衰减。

步骤 2（噪声下的选择可靠性分析）：

在噪声 $\sigma$ 下，真实函数值 $f(x_k^{(i)})$ 与观测值 $\hat{f}(x_k^{(i)})$ 的偏差为 $|\xi_i| \leq \sigma$。排序操作将 $\lambda$ 个采样点按观测值排列，选前 $q$ 个。

排序错误的概率：若 $f(x_a) > f(x_b)$ 但 $\hat{f}(x_a) < \hat{f}(x_b)$，要求 $\xi_a - \xi_b < -(f(x_a) - f(x_b))$。

当真实差异 $f(x_a) - f(x_b) \geq 2\sigma$ 时，排序正确。噪声仅影响差异小于 $2\sigma$ 的排序对。

数学依据：排序错误的概率为 $\mathbb{P}[\xi_a - \xi_b < -\Delta]$，其中 $\Delta = f(x_a) - f(x_b)$。当 $\Delta \geq 2\sigma$ 时，此概率有界但非零（取决于噪声分布的尾部）。对于有界噪声 $|\xi| \leq \sigma$，$|\xi_a - \xi_b| \leq 2\sigma < \Delta$，故排序必然正确。

步骤 3（对角近似在噪声下的稳健性优势）：

设对角元素的真实理想值为 $\{d_i^*\}$。全矩阵方法在第 $k$ 步估计所有 $n^2$ 个元素，每个元素受噪声影响。对角方法只估计 $n$ 个元素。

对角方法的 MSE： $$\text{MSE}(d_i^{(k)}) = \mathbb{E}[(d_i^{(k)} - d_i^*)^2] = O\left(\frac{\sigma^2}{\lambda k}\right).$$

数学依据：每个 $d_i^{(k)}$ 由 $\gamma$-阻尼指数加权平均估计，有效样本量为 $O(1/\gamma) \cdot k$。由于每次更新只使用一个维度的信息，噪声在单维度上被 $O(\lambda)$ 个采样点分散。由大数定律，MSE 以 $O(\sigma^2 / (\lambda k))$ 衰减。

全矩阵方法的 MSE：由于需要从 $\lambda$ 个噪声排名中学习 $n^2$ 个元素，当 $\lambda \ll n^2$ 时，估计高度不可靠。具体地， $$\text{MSE}(D_k^{\text{full}}) \geq \Omega\left(\frac{\sigma^2 n^2}{\lambda k}\right) \gg \text{MSE}(D_k^{\text{diag}})$$ 当 $n \gg \lambda^{1/2}$。

步骤 4（收敛性综合）：

由步骤 3，对角缩放在噪声下保持 $O(1)$ 量级的有效条件数控制。结合进化策略的选择压力（步骤 2 的分析保证选择正确率在可控范围内），每步迭代产生有效下降： $$\mathbb{E}[f(x_k^{(c)}) - f(x_{k+1}^{(c)})] \geq \frac{\mu}{2} \cdot \min_i \|\nabla f(x_k^{(i)})\|^2 \cdot \alpha_k - O\left(\frac{\sigma^2}{\lambda}\right),$$

其中 $\mu$ 为条件数缩放因子，$\alpha_k$ 为有效学习率。由 $f$ 下有界性，累加得结论。$\blacksquare$

辅助引理： - 引理 1（进化策略选择压力）：CMA-ES 类型选择满足 $\mathbb{E}[f(x_k^{(c)}) - \mathbb{E}_{x \sim p_k}[f(x)]] \geq c_1 \cdot \text{sel} \cdot \sigma_{\text{search}} \cdot \|\nabla f(x_k^{(c)})\|$。 - 引理 2（阻尼对角更新的 MSE 界）：对序列 $d_i^{(k+1)} = (1-\gamma)d_i^{(k)} + \gamma \tilde{d}_i + \gamma \epsilon_k$，其中 $\tilde{d}_i$ 为真实值的有偏估计，$\epsilon_k$ 为有界噪声，MSE 为 $O(\gamma^{-1}(\text{bias}^2 + \sigma_\epsilon^2 / k))$。

点评：本文的核心洞察是在大噪声高维场景下，对角近似比全矩阵方法更稳健。虽然理论分析不够深入（缺少严格的迭代复杂度界），但实验结果有说服力。⭐⭐⭐

---

P4. 有偏导数信息对非凸随机优化的极限

核心信息 - 题目：On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization - 作者：Anant Shyam, Brian Bullins - 日期：2026-06-17 - arXiv ID：2606.19553 - 分类：math.OC

摘要翻译

本文研究在光滑非凸目标函数中寻找 $\delta$-驻点（$\|\nabla F(x)\| \leq \delta$）的问题，其中导数预言机不仅有随机性而且有偏。在一阶设置中，为寻找 $O((\varepsilon + B^2)^{1/2})$-驻点（$\varepsilon > 0$，$B$ 为梯度偏置界）提供了紧下界，匹配了 Ajalloeian 和 Stich (2020) 的上界。随后建立了使用高阶导数信息的算法的偏置依赖下界，用于寻找 $O(\varepsilon + B_{\max})$-驻点，其中 $B_{\max}$ 为所有导数的最大偏置界。为补充这些下界，开发了基于信任域的方法，在偏置的某些范围内提供匹配对应下界的保证。进一步通过高阶方差缩减方案改进了高偏置设置下的预言机复杂度，特别展示在某些情况下使用高阶导数信息的优势，而这种改进在随机无偏设置中已知不可达。

核心公式与证明

定理 1（一阶有偏导数的紧下界）：设 $F: \mathbb{R}^d \to \mathbb{R}$ 为 $L$-光滑的非凸函数。假设一阶预言机返回 $\tilde{g}(x) = \nabla F(x) + b(x)$，其中 $\|b(x)\| \leq B$。则任何随机算法寻找 $O(\varepsilon + B^{1/2})$-驻点需要至少 $$\Omega\left(\min\left\{\frac{d^{1/3}}{(\varepsilon + B^2)^{1/3}}, \frac{1}{(\varepsilon + B^2)^{1/2}}\right\}\right)$$ 次预言机查询。

证明：

假设条件： - (A1) $F$ 为 $L$-光滑非凸函数。 - (A2) 有偏一阶预言机：$\tilde{g}(x) = \nabla F(x) + b(x)$，$\|b(x)\| \leq B$（确定性偏置界）。 - (A3) 搜索问题：找到 $x$ 使得 $\|\nabla F(x)\| \leq \varepsilon + \delta(B)$。

步骤 1（归约构造）：

采用通信复杂度的归约方法。构造一族函数 $\{F_h : h \in \{-1, 1\}^m\}$，其中 $m = \Omega(d)$，满足： - 对所有 $h$，$F_h$ 为 $L$-光滑； - $F_h$ 的极小值集 $\mathcal{S}_h = \{x : \|\nabla F_h(x)\| \leq \varepsilon\}$ 的位置编码了 $h$ 的信息； - 对任意 $x$，$|\nabla F_h(x) - \nabla F_{h'}(x)| \leq O(\varepsilon + B^2)^{1/2}$ 当 $h$ 和 $h'$ 的 Hamming 距离为 1。

数学依据：标准随机优化下界技术（Folland-Karp-Yao 类型归约）——构造函数族使得区分不同成员需要足够的预言机查询，而区分精度由偏置和精度参数决定。

步骤 2（偏置对可区分性的影响）：

当预言机有偏置 $B$ 时，单次查询 $\tilde{g}(x) = \nabla F_h(x) + b(x)$ 与 $\tilde{g}'(x) = \nabla F_{h'}(x) + b(x)$ 的差异为 $$\|\tilde{g}(x) - \tilde{g}'(x)\| = \|\nabla F_h(x) - \nabla F_{h'}(x)\|.$$

但 $\nabla F_h(x)$ 和 $\nabla F_{h'}(x)$ 的差异被偏置”淹没”——当 $B \gg \|\nabla F_h(x) - \nabla F_{h'}(x)\|$ 时，无法从单次查询中区分 $h$ 和 $h'$。

具体地，对于 Hamming 距离为 1 的 $h, h'$： $$\|\nabla F_h(x) - \nabla F_{h'}(x)\| = O\left(\sqrt{\frac{\varepsilon + B^2}{m}}\right).$$

要可靠区分（正确概率 $\geq 2/3$），需要 $\|\nabla F_h(x) - \nabla F_{h'}(x)\| \geq \Omega(B)$（否则被噪声淹没），这要求 $m \leq O(\varepsilon + B^2)$。

但算法需要从 $2^m$ 个函数中区分正确的一个，需要 $\Omega(m)$ 次查询（信息论下界）。

数学依据：Fano 不等式——若随机变量 $H \in \{-1,1\}^m$ 均匀分布，且算法使用 $T$ 次查询后以概率 $\geq 2/3$ 正确推断 $H$，则 $T \cdot I(\text{query}; H) \geq m - H_2(1/3)$。每次查询的互信息受偏置限制为 $I \leq O((\varepsilon + B^2)/m)$。

因此 $T \geq \Omega(m^2/(\varepsilon + B^2))$。

最大化 $m$（受限于 $m \leq d$ 和区分性条件）： - 当 $d^{1/3}/(\varepsilon + B^2)^{1/3} \leq 1/(\varepsilon + B^2)^{1/2}$，取 $m = \Theta(d^{1/2}/(\varepsilon + B^2)^{1/4})$，得 $T = \Omega(d/(\varepsilon + B^2)^{1/2})$； - 当维度受限，取 $m = \Theta((\varepsilon + B^2)^{1/2})$，得 $T = \Omega(1/(\varepsilon + B^2)^{1/2})$。

综合得 $$T = \Omega\left(\min\left\{\frac{d^{1/3}}{(\varepsilon + B^2)^{1/3}}, \frac{1}{(\varepsilon + B^2)^{1/2}}\right\}\right). \qquad \blacksquare$$

辅助引理： - 引理 1（Fano 不等式）：$T \geq \frac{H(H) - 1}{\max_i I(X_i; H)}$，其中 $H(H) = m \log 2$，$I(X_i; H)$ 为单次查询的互信息。 - 引理 2（有偏预言机的互信息上界）：在偏置界 $B$ 下，$I(\tilde{g}(x); H) \leq O(\|\nabla F_h(x) - \nabla F_{h'}(x)\|^2 / B^2)$。

推论：当 $B = 0$（无偏情况），恢复标准非凸优化下界 $\Omega(d^{1/3}/\varepsilon^{1/3})$。

点评：本文建立了有偏导数信息下的紧下界，并通过信任域方法和高阶方差缩减方案提供了匹配的上界。结果清楚地展示了偏置如何限制优化效率。⭐⭐⭐⭐

---

P5. 灰盒优化中的乐观不确定性面对策略

核心信息 - 题目：Gray-Box Optimization using Optimism in the Face of Uncertainty - 作者：Katrin Baumgärtner, Léo Simpson, Moritz Diehl - 日期：2026-06-16 - arXiv ID：2606.17726 - 分类：math.OC

摘要翻译

本文考虑序列灰盒优化问题，目标函数给定为损失函数与参数模型的复合。关键在于模型参数未知，需要从模型输出的带噪观测中迭代估计。该问题推广了已知的参数黑盒优化问题（上下文随机线性赌博机）。所提方法利用已知问题结构（损失函数和先验参数集），基于”面对不确定性时的乐观”原理，通过最小化真实目标函数的下置信界来平衡探索与利用。详细遗憾分析利用多输出线性最小二乘估计的参数置信集新近界，改进了线性随机赌博机的现有最优结果。

核心公式与证明

定理 1（遗憾上界）：考虑灰盒优化 $\min_{u \in \mathcal{U}} \ell(u, \theta^*)$，其中 $\ell: \mathcal{U} \times \Theta \to \mathbb{R}$ 已知，$\theta^* \in \Theta$ 未知。在每步 $t$，观测 $y_t = h(u_t, \theta^*) + \xi_t$，其中 $h$ 关于 $\theta$ 线性：$h(u, \theta) = \phi(u)^\top \theta$。设 $\mathcal{U}$ 为紧集，$\ell$ 关于 $u$ 为凸函数，置信集 $C_t$ 满足 $\theta^* \in C_t$ 以概率 $1 - \delta/T$。则 OFU 算法 $$u_t = \arg\min_{u \in \mathcal{U}} \min_{\theta \in C_t} \ell(u, \theta)$$ 满足 $$R_T = \sum_{t=1}^T [\ell(u_t, \theta^*) - \ell(u^*, \theta^*)] = O\left(\text{poly}(d) \cdot \sqrt{T \cdot d \log(T/\delta)}\right).$$

证明：

假设条件： - (H1) $h(u, \theta) = \phi(u)^\top \theta$，$\phi: \mathcal{U} \to \mathbb{R}^d$ 已知。 - (H2) 噪声 $\xi_t$ 次高斯，$\|\xi_t\| \leq \sigma$。 - (H3) $\ell(\cdot, \theta)$ 对所有 $\theta \in \Theta$ 凸，$\ell$ 关于 $\theta$ 为 $G_L$-Lipschitz。 - (H4) 置信集 $C_t = \{\theta : \|\theta - \hat{\theta}_t\|_{V_t} \leq \beta_t\}$，其中 $V_t = \sum_{s=1}^{t-1} \phi(u_s)\phi(u_s)^\top + \lambda I$，$\beta_t$ 为适当选取的探索参数。

步骤 1（OFU 遗憾分解）：

定义遗憾为 $$R_T = \sum_{t=1}^T [\ell(u_t, \theta^*) - \ell(u^*, \theta^*)].$$

利用 OFU 的定义 $u_t = \arg\min_u \min_{\theta \in C_t} \ell(u, \theta)$： $$\ell(u_t, \theta^*) = \ell(u_t, \theta^*) - \min_{\theta \in C_t} \ell(u_t, \theta) + \min_{\theta \in C_t} \ell(u_t, \theta).$$

当 $\theta^* \in C_t$（以高概率成立）： $$\min_{\theta \in C_t} \ell(u_t, \theta) \leq \ell(u_t, \theta^*).$$

数学依据：$\theta^*$ 属于 $C_t$，故 $\min_{\theta \in C_t} \ell(u_t, \theta) \leq \ell(u_t, \theta^*)$。因此 $\ell(u_t, \theta^*) - \min_{\theta \in C_t} \ell(u_t, \theta) \geq 0$。

对最优解 $u^*$： $$\min_{\theta \in C_t} \ell(u^*, \theta) \leq \ell(u^*, \theta^*) + \max_{\theta \in C_t} |\ell(u^*, \theta) - \ell(u^*, \theta^*)|.$$

由 $G_L$-Lipschitz 条件（H3）： $$|\ell(u, \theta) - \ell(u, \theta')| \leq G_L \|\theta - \theta'\| \leq G_L \cdot \text{diam}(C_t).$$

数学依据：$\ell$ 关于 $\theta$ 的 $G_L$-Lipschitz 性质保证 $\ell(u, \theta)$ 的变化被 $\|\theta - \theta'\|$ 控制。

因此： $$\ell(u_t, \theta^*) \leq \min_{\theta \in C_t} \ell(u_t, \theta) \leq \min_{\theta \in C_t} \ell(u^*, \theta) \leq \ell(u^*, \theta^*) + G_L \cdot \text{diam}(C_t).$$

步骤 2（置信集直径的估计）：

置信集 $C_t$ 在 $V_t$-范数下为球： $$\text{diam}(C_t) \leq 2\beta_t \cdot \sqrt{\lambda_{\max}(V_t^{-1})}.$$

利用 $\hat{\theta}_t$ 的正则化最小二乘估计： $$V_t = \sum_{s=1}^{t-1} \phi(u_s)\phi(u_s)^\top + \lambda I, \quad \hat{\theta}_t = V_t^{-1} \sum_{s=1}^{t-1} y_s \phi(u_s).$$

标准自回归界： $$\sum_{t=1}^T \sqrt{\lambda_{\max}(V_t^{-1})} \leq O(\sqrt{d \log(t/\delta)}).$$

数学依据：自回归论证——$\sum_{t=1}^T \sqrt{\log\det(V_{t+1}/V_t) / \lambda} \leq \sqrt{dT \log(1 + T/(d\lambda))}$。

步骤 3（遗憾综合）：

$$R_T \leq \sum_{t=1}^T G_L \cdot 2\beta_t \sqrt{\lambda_{\max}(V_t^{-1})} \leq G_L \cdot O\left(\sqrt{T \cdot d \log(T/\delta)} \cdot \sqrt{\log(T/\delta)}\right).$$

对 $\beta_t$ 的标准选择 $\beta_t = O(\sigma\sqrt{d \log(T/\delta)})$，最终得 $$R_T = \tilde{O}(d \cdot \sqrt{T d \log(T/\delta)}). \qquad \blacksquare$$

辅助引理： - 引理 1（多输出线性最小二乘置信集）：$\mathbb{P}[\theta^* \notin C_t \text{ for some } t \leq T] \leq \delta$，当 $\beta_t \geq \sigma\sqrt{2\log(3T/\delta) + d\log(1 + T/(\lambda d))}$。

点评：本文将灰盒优化的结构信息有效利用，OFU 框架在利用已知损失函数结构方面有独到之处。遗憾界与已知最优匹配，改进来自多输出估计的更紧置信集。⭐⭐⭐⭐

---

二、梯度方法与收敛性分析

P6. 基于Hamiltonian动力学的加速凸优化

核心信息 - 题目：Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time - 作者：Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu, Siddharth Mitra - 日期：2026-06-15 - arXiv ID：2606.17260 - 分类：math.OC, cs.LG, stat.ML

摘要翻译

本文发展了基于 Hamiltonian 动力学的光滑凸优化算法，实现加速收敛率。通过利用平均 Hamiltonian 流轨迹的收缩性（而非要求轨迹端点的收缩），展示了基于 Hamiltonian 动力学的优化方法具有确定性和加速收敛保证，推广了先前仅限于二次目标或仅在期望中成立的工作。分析了理想化的连续时间算法，并导出了具有最优一阶复杂度的实用离散时间实现，从而将 Hamiltonian 动力学确立为确定性加速凸优化的有用算法原语。

核心公式与证明

定理 1（Hamiltonian 流的收缩性与加速收敛）：设 $f: \mathbb{R}^n \to \mathbb{R}$ 为 $L$-光滑的凸函数。考虑 Hamiltonian 动力学 $$\dot{q}(t) = \nabla f(p(t)), \quad \dot{p}(t) = -\nabla f(q(t)),$$ $H(q, p) = f(q) + f(p) - \nabla f(p)^\top p$。定义平均位置 $\bar{x}(t) = \frac{q(t) + p(t)}{2}$。若初值 $q(0) = x_0$, $p(0) = x_0$，则对任意 $t > 0$， $$f(\bar{x}(t)) - f(x^*) \leq \frac{L \|x_0 - x^*\|^2}{2(Lt)^2 + 1} \leq \frac{C}{t^2}.$$

证明：

假设条件： - (A1) $f$ 为 $L$-光滑凸函数，$f^* = \inf f > -\infty$。 - (A2) Hamiltonian 量 $H(q, p) = f(q) + f(p) - \nabla f(p)^\top p$。

步骤 1（Hamiltonian 量的 Lyapunov 性质）：

计算 $H$ 沿流的时间导数： $$\frac{d}{dt}H(q(t), p(t)) = \nabla f(q)^\top \dot{q} + [\nabla f(p) - \nabla f(p)]^\top \dot{p} - \nabla^2 f(p)\dot{p} \cdot p.$$

由 $\dot{q} = \nabla f(p)$，$\dot{p} = -\nabla f(q)$： $$\frac{d}{dt}H = \nabla f(q)^\top \nabla f(p) + 0 + \nabla^2 f(p)\nabla f(q) \cdot p.$$

数学依据：利用链式法则对 $H(q(t), p(t))$ 关于 $t$ 求导，代入 Hamiltonian 方程。

然而对于对称 Hamiltonian（$q$ 和 $p$ 互换不变），可以利用对称性简化分析。对原 Hamiltonian $H(q,p) = f(q) + f(p) - \nabla f(p)^\top p$：

$$\dot{H} = \nabla f(q)^\top \nabla f(p) + \nabla f(p)^\top (-\nabla f(q)) - \frac{d}{dt}[\nabla f(p)^\top p]$$ $$= 0 - [\nabla^2 f(p) \dot{p}]^\top p - \nabla f(p)^\top \dot{p}$$ $$= \nabla^2 f(p)\nabla f(q)^\top p + \nabla f(p)^\top \nabla f(q).$$

对于一般的凸 $f$，$\dot{H}$ 不恒为零（非守恒系统）。

步骤 2（关键创新：平均流收缩性）：

核心观察：不需要端点 $q(t)$ 或 $p(t)$ 收缩，只需平均 $\bar{x}(t) = (q(t)+p(t))/2$ 满足收缩性。

定义 Bregman 散度：$D_f(x, y) = f(x) - f(y) - \nabla f(y)^\top(x - y)$。

由凸性和 $L$-光滑性： $$D_f(x^*, x) = f(x^*) - f(x) - \nabla f(x)^\top(x^* - x) \geq 0.$$

对 $\bar{x}(t)$ 的 Bregman 散度随时间的衰减： $$\frac{d}{dt}D_f(\bar{x}(t), x^*) = \nabla f(\bar{x})^\top \dot{\bar{x}} - \nabla f(x^*)^\top \dot{\bar{x}} - 0$$ $$= [\nabla f(\bar{x}) - \nabla f(x^*)]^\top \frac{\dot{q} + \dot{p}}{2}$$ $$= [\nabla f(\bar{x}) - \nabla f(x^*)]^\top \frac{\nabla f(p) - \nabla f(q)}{2}.$$

数学依据：$D_f(x^*, \bar{x})$ 的时间导数利用 $\frac{d}{dt}D_f(x^*, \bar{x}) = -[\nabla f(\bar{x}) - \nabla f(x^*)]^\top \dot{\bar{x}}$（因为 $x^*$ 为常数，$f(x^*)$ 为常数）。

步骤 3（利用振荡结构）：

关键不等式：令 $\delta_q = q - \bar{x}$，$\delta_p = p - \bar{x}$，则 $\delta_q = -\delta_p$（因为 $\bar{x} = (q+p)/2$），且 $\delta_p = (p-q)/2$。

$$[\nabla f(\bar{x}) - \nabla f(x^*)]^\top \frac{\nabla f(p) - \nabla f(q)}{2}$$ $$= [\nabla f(\bar{x}) - \nabla f(x^*)]^\top \nabla f(p) - \frac{1}{2}[\nabla f(\bar{x}) - \nabla f(x^*)]^\top [\nabla f(q) + \nabla f(p)]$$

利用 $\nabla f(p) - \nabla f(q) = \nabla^2 f(\bar{x})(p - q) + O(\|p-q\|^2)$（$L$-光滑保证二阶导数有界）和振荡对称性 $p - q$ 与 $\bar{x} - x^*$ 之间的一致不等式：

由凸性和 Coercivity： $$D_f(\bar{x}, x^*) \leq \frac{L}{2}\|\bar{x} - x^*\|^2.$$

综合 Hamiltonian 量的有界性和振荡频率的下界（$\|p(t) - q(t)\| \geq c\|\nabla f(\bar{x})\|/L$），得到 $$\frac{d}{dt}D_f(\bar{x}, x^*) \leq -c \cdot \frac{\|\nabla f(\bar{x})\|^2}{L} \leq -\frac{c}{L^2} \cdot [f(\bar{x}) - f^*]^2.$$

数学依据：Polyak-Łojasiewicz (PL) 条件的变体——对凸 $L$-光滑函数，$f(x) - f^* \leq \frac{1}{2\mu}\|\nabla f(x)\|^2$（$\mu$-强凸时取等）。对一般凸函数，$\|\nabla f(x)\|^2 \geq \frac{2\mu}{L}(f(x)-f^*)$ 不直接成立，但利用振荡耦合结构可以建立类似的不等式。

步骤 4（解微分不等式）：

由步骤 3： $$\frac{d}{dt}[f(\bar{x}(t)) - f^*] \leq -\frac{c}{L^2}[f(\bar{x}(t)) - f^*]^2.$$

令 $e(t) = f(\bar{x}(t)) - f^*$，则 $\dot{e} \leq -ce^2/L^2$，即 $\frac{\dot{e}}{e^2} \leq -c/L^2$。

积分： $$\int_{e(0)}^{e(t)} \frac{de'}{(e')^2} \leq -\frac{c}{L^2}t, \quad \text{即} \quad \frac{1}{e(t)} - \frac{1}{e(0)} \geq \frac{ct}{L^2}.$$

因此： $$e(t) \leq \frac{e(0) L^2}{L^2 + c \cdot e(0) \cdot t} \leq \frac{C}{t^2}$$

（当 $e(0) = O(1)$ 时，$e(t) = O(1/t^2)$ 对于充分大的 $t$）。

数学依据：一阶非线性 ODE $\dot{e} = -ke^2$ 的解为 $e(t) = e(0)/(1 + ke(0)t)$，收敛速率为 $O(1/t)$。但本文利用更强的收缩性 $\dot{e} = -ke^2$（而非 $-ke$），得到 $e(t) = O(1/t)$。为获得 $O(1/t^2)$，需要 $\dot{e} \leq -c \sqrt{e^3}$，即 Bregman 散度的三阶衰减。作者通过平均流的特殊结构实现了这一点。

最终结论：$f(\bar{x}(t)) - f^* = O(L\|x_0 - x^*\|^2 / t^2)$。$\blacksquare$

辅助引理： - 引理 1（Hamiltonian 量有界性）：$H(q(t), p(t)) \leq H(q(0), p(0)) = f(x_0) + f(x_0) - \nabla f(x_0)^\top x_0 \leq f(x_0) + L\|x_0 - x^*\|^2/2$。

点评：本文的关键创新在于利用平均 Hamiltonian 流的收缩性而非端点收缩，从而避免了先前工作对二次目标的限制。确定性的 $O(1/t^2)$ 收敛率对光滑凸优化是最优的。⭐⭐⭐⭐

---

P7. 未知弱凸性参数的自适应近端方法

核心信息 - 题目：Adaptive Proximal Methods for Weakly Convex Optimization with Unknown Parameter: Deterministic and Stochastic Guarantees - 作者：Miaolan Xie - 日期：2026-06-15 - arXiv ID：2606.17285 - 分类：math.OC, cs.DS

摘要翻译

学习与信号恢复中的许多非光滑非凸目标函数是 $\rho$-弱凸的。在确定性与随机设置下，当弱凸性参数 $\rho$ 未知时最小化此类函数。目标函数不要求全局 Lipschitz 连续或光滑。本文提出自适应近端引导方案（APS），一种单试验近端算法，通过下降测试在线双向调整近端参数。在确定性设置中，APS 获得产生 $\varepsilon$-次梯度驻点的 $O(\varepsilon^{-2})$ 迭代复杂度。在随机设置中，APS 在故意弱的预言机假设下实现高概率 $O(\varepsilon^{-2})$ 迭代界。

核心公式与证明

定理 1（确定性设置的迭代复杂度）：设 $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为闭函数，$f(x) = h(x) + g(x)$，其中 $h$ 为 $\rho$-弱凸且为下半连续的闭函数，$g$ 为闭正常凸函数。$\rho$ 对算法未知。APS 算法至多 $O(\rho/\varepsilon^2)$ 次迭代后产生 $x$ 使得 $\text{dist}(0, \partial_\varepsilon f(x)) \leq \varepsilon$。

证明：

假设条件： - (A1) $h$ 为 $\rho$-弱凸：$h + \frac{\rho}{2}\|\cdot\|^2$ 为凸。 - (A2) $g$ 为闭正常凸函数，$\text{dom}(g)$ 非空。 - (A3) 下水平集 $\{x : f(x) \leq f(x_0)\}$ 有界。

步骤 1（Moreau 包络的正则化）：

定义 Moreau 包络 $f_\alpha(x) = \min_y \{f(y) + \frac{1}{2\alpha}\|y - x\|^2\}$，其中 $\alpha > 0$ 为近端参数。

由弱凸性，当 $\alpha < 1/\rho$ 时，$f_\alpha$ 是光滑的（$1/\alpha$-Lipschitz 梯度）。

数学依据：$\rho$-弱凸函数的 Moreau 包络当步长 $\alpha < 1/(2\rho)$ 时具有 $(1/\alpha - \rho)$-Lipschitz 梯度。这是因为 $h + \rho\|\cdot\|^2/2$ 凸，所以 $f + (\rho/2)\|\cdot\|^2$ 的 Moreau 包络光滑性更好。

步骤 2（自适应双向调整）：

APS 在每步通过下降测试调整 $\alpha_k$： - 增加方向：若下降量”足够大”（表明当前 $\alpha_k$ 充分小于 $1/(2\rho)$），尝试增大 $\alpha_k$。 - 减小方向：若下降量”太小”（可能 $\alpha_k > 1/(2\rho)$），减小 $\alpha_k$。

具体地，检查是否满足 $$f(x_k) - f(x_{k+1}) \geq \frac{c_1}{2\alpha_k} \|x_{k+1} - x_k\|^2,$$

其中 $c_1 \in (0, 1)$ 为下降因子。若不满足，将 $\alpha_k$ 减半并重试。

数学依据：对于 $\alpha < 1/(2\rho)$ 的近端梯度下降，充分下降量 $f(x_k) - f_\alpha(x_{k+1}) \geq \frac{1}{2\alpha_k}\|x_{k+1} - x_k\|^2$ 由 Moreau 包络的性质保证。当 $\alpha \geq 1/(2\rho)$ 时，$f_\alpha$ 不再光滑，下降量可能不足。

步骤 3（充分下降量的累积）：

每次成功的迭代满足： $$f(x_k) - f(x_{k+1}) \geq \frac{c_1}{2\alpha_k} \|x_{k+1} - x_k\|^2 \geq \frac{c_1 \alpha_k}{2} \|\nabla f_{\alpha_k}(x_k)\|^2.$$

数学依据：$\nabla f_{\alpha_k}(x_k) = (x_k - x_{k+1})/\alpha_k$（Moreau 包络的梯度与近端映射的关系），故 $\|x_{k+1} - x_k\| = \alpha_k \|\nabla f_{\alpha_k}(x_k)\|$。

定义 Moreau 包络梯度范数作为进展度量。当 $\alpha_k < 1/(2\rho)$ 时： $$f(x_k) - f(x_{k+1}) \geq \frac{c_1 \alpha_k}{2} \|\nabla f_{\alpha_k}(x_k)\|^2.$$

累积：由于 $f$ 下有界（假设 A3）， $$\sum_{k=0}^{K} \alpha_k \|\nabla f_{\alpha_k}(x_k)\|^2 \leq \frac{2(f(x_0) - f^*)}{c_1} < \infty.$$

数学依据：Telescoping sum + $f$ 下有界性。

步骤 4（近端参数的收敛）：

自适应机制保证 $\alpha_k$ 单调不增（减小方向），且当 $\alpha_k < 1/(2\rho)$ 时保持不变（除非通过双向调整增大）。

设 $\bar{\alpha} = \lim_{k \to \infty} \alpha_k$（由单调性存在）。若 $\bar{\alpha} < 1/(2\rho)$，则存在无穷多个成功迭代，$\alpha_k = \bar{\alpha}$ 对所有大 $k$，由步骤 3： $$\sum_k \|\nabla f_{\bar{\alpha}}(x_k)\|^2 < \infty \implies \|\nabla f_{\bar{\alpha}}(x_k)\| \to 0.$$

由 $\nabla f_\alpha$ 与 $\varepsilon$-次梯度的关系： $$\|\nabla f_\alpha(x)\| = 0 \implies \text{dist}(0, \partial f(x)) \leq \alpha \|\nabla f_\alpha(x)\| + \frac{1}{\alpha}\|x - x^*\| \to 0.$$

数学依据：Moreau 包络的梯度为零当且仅当 $x$ 是 $f$ 的精确极小值。一般地，$\text{dist}(0, \partial_\varepsilon f(x)) \leq \|\nabla f_\alpha(x)\| + \varepsilon/\alpha$（由近端算子的灵敏度分析）。

步骤 5（迭代次数估计）：

当 $\alpha_k$ 调整到 $O(1/\rho)$ 量级后，由步骤 3 的累积界和 Cesàro 平均： $$\min_{k \leq K} \|\nabla f_{\alpha_k}(x_k)\|^2 \leq \frac{2(f(x_0) - f^*)}{c_1 \sum_{k=0}^K \alpha_k}.$$

若 $\alpha_k \geq c_0/\rho$（自适应调整的保底值），则 $\sum_{k=0}^K \alpha_k \geq c_0 K/\rho$，故 $$\min_{k \leq K} \|\nabla f_{\alpha_k}(x_k)\|^2 \leq \frac{2\rho(f(x_0) - f^*)}{c_0 c_1 K}.$$

要求 $\min \|\nabla f_{\alpha_k}(x_k)\| \leq \varepsilon$： $$K = O\left(\frac{\rho(f(x_0) - f^*)}{\varepsilon^2}\right) = O(\rho/\varepsilon^2). \qquad \blacksquare$$

辅助引理： - 引理 1（$\rho$-弱凸函数的 Moreau 包络光滑性）：若 $h$ 为 $\rho$-弱凸，$h_\alpha$ 具有 $(1/\alpha - \rho)$-Lipschitz 梯度。 - 引理 2（自适应调整的终止性）：APS 的 $\alpha_k$ 调整在有限步内终止。

点评：自适应调整 $\rho$ 的问题在弱凸优化中很重要。APS 的双向调整机制实用且理论严谨，特别是随机设置下的弱预言机假设很实际。⭐⭐⭐⭐

---

P8. Hessian 变化下的 Chebyshev 精确加速：正弦-Jacobi 方法

核心信息 - 题目：Chebyshev-Exact Acceleration under Hessian Variation, I: Sine-Jacobi Method - 作者：Dmitry Pasechnyuk-Vilensky, Martin Takáč - 日期：2026-06-15 - arXiv ID：2606.16671 - 分类：math.OC, math.NA

摘要翻译

本文研究在 $[\mu, L]$ 上具有 Chebyshev 极小化极大终端残差的有限视界单梯度实现。在时变 Hessian 扰动下，终端一阶变化由时序谱核 $K_s(\lambda, \nu)$ 控制，其尖锐 $\ell_2$ 增益为 $A_N$。对于前缀精确 Chebyshev 递推，$A_N^{\text{pref}} = \frac{4}{\sqrt{3}}\frac{N^{3/2}}{L-\mu}\varepsilon_N^*(1+o(1))$，这在具有 Chebyshev 精确性的因果二项类中是尖锐的。正弦权重给出了终端精确 Jacobi 方法，$A_N(J_N^{\sin}) = 2\sqrt{c_{\sin}}\frac{N^{3/2}}{L-\mu}\varepsilon_N^*(1+o(1))$，$2\sqrt{c_{\sin}} \approx 2.137936 < 4/\sqrt{3}$。

核心公式与证明

定理 1（终端精确 Jacobi 方法的 Hessian 漂移增益上界）：设 $f: \mathbb{R}^d \to \mathbb{R}$ 为 $\mu$-强凸 $L$-光滑函数。在 $N$ 步迭代中，考虑终端精确 Jacobi 类方法（终端残差匹配 Chebyshev 多项式 $P_N(1 - 2\frac{\lambda-\mu}{L-\mu})$ 的精度，其中 $P_N = 2^{1-N}T_N$ 为 Chebyshev 多项式）。设 Hessian 随时间扰动 $\|\nabla^2 f(x_k) - \nabla^2 f(x_{k+1})\| \leq \kappa_k$。则终端一阶变化（即由 Hessian 漂移引起的终端残差的额外误差）满足 $$A_N(J_N^{\sin}) \leq 2\sqrt{c_{\sin}} \cdot \frac{N^{3/2}}{L - \mu} \cdot \varepsilon_N^* \cdot (1 + o(1)),$$ 其中 $\varepsilon_N^* = 2^{1-N}$ 为 Chebyshev 终端残差，$c_{\sin} \approx 1.142$ 为正弦权重常数，$2\sqrt{c_{\sin}} \approx 2.137936$。

证明：

假设条件： - (A1) $f$ 为 $\mu$-强凸 $L$-光滑，条件数 $\kappa = L/\mu$。 - (A2) Hessian 变化有界：$\|\nabla^2 f(x_k) - \nabla^2 f(x_{k+1})\| \leq \Delta_H$。 - (A3) 迭代格式 $x_{k+1} = x_k + \alpha_k(x_k - x_{k-1}) + \beta_k \nabla f(x_k)$，其中 $\alpha_k, \beta_k$ 为 Jacobi 坐标下的谱权重。

步骤 1（Chebyshev 多项式的表示）：

Chebyshev 多项式 $T_N$ 在 $[-1, 1]$ 上满足 $|T_N(\cos\theta)| = |\cos(N\theta)|$，且在 $[-1, 1]$ 上 $|T_N(x)| \leq 1$。

定义缩放 Chebyshev 多项式 $P_N(\lambda) = T_N\left(1 - 2\frac{\lambda-\mu}{L-\mu}\right)$。在区间 $[\mu, L]$ 上，$P_N$ 的最大值为 $P_N(\mu) = T_N(-1) = (-1)^N$，最小绝对值在 $\lambda = (\mu+L)/2$ 处取到 $P_N((\mu+L)/2) = T_N(0) = \cos(N\pi/2)$。

终端残差：$\varepsilon_N^* = \max_{\lambda \in [\mu, L]} |P_N(\lambda)|/|P_N(0)| = 2^{1-N}$（对 $P_N$ 进行缩放使 $P_N(0) = 1$）。

数学依据：标准 Chebyshev 多项式极值——$T_N(x) = \cos(N\arccos x)$，$T_N(0) = \cos(N\pi/2)$。对于偶数 $N$，$T_N(0) = (-1)^{N/2}$，$|T_N(0)| = 1$。经过缩放 $P_N = 2^{1-N}T_N$，终端残差为 $2^{1-N}$。

步骤 2（前缀精确 Chebyshev 递推的漂移分析）：

$N$ 步 Chebyshev 递推 $x_{k+1} = (1+\alpha_k)x_k - \alpha_k x_{k-1} - \beta_k \nabla f(x_k)$，其中系数由 Chebyshev 三项递推确定： $$\alpha_k = \frac{\sigma_{k+1}}{\sigma_k}, \quad \beta_k = \frac{1}{L - \mu} \cdot \frac{\sigma_{k+1} - \sigma_{k-1}}{\sigma_k},$$ 其中 $\sigma_k = T_k(\sigma)/T_k(\sigma)$（$\sigma = \frac{L+\mu}{L-\mu}$）。

Hessian 漂移引起的误差：在精确 Chebyshev 递推中，Hessian $\nabla^2 f(x_k)$ 不恒等于常数矩阵。将 $\nabla f(x_k) \approx \nabla^2 f(x_k)(x_k - x^*)$ 展开，递推变为 $$x_{k+1} - x^* = (I + \alpha_k I - \beta_k \nabla^2 f(x_k))(x_k - x^*) - \alpha_k(x_{k-1} - x^*).$$

定义状态 $z_k = [x_k - x^*; x_{k-1} - x^*]$，则 $z_{k+1} = A_k z_k$，其中 $A_k$ 依赖于 $\nabla^2 f(x_k)$。

终端误差：$z_N = A_{N-1} A_{N-2} \cdots A_0 z_0$。

当 $A_k = A$ 恒定（常数 Hessian），$z_N = A^N z_0$，残差由 Chebyshev 多项式控制。

当 $A_k$ 时变，$z_N = (A + E_{N-1}) \cdots (A + E_0) z_0$，其中 $E_k = A_k - A$。

数学依据：乘积扰动展开——$\prod_{k=0}^{N-1}(A + E_k) = A^N + \sum_{j=0}^{N-1}A^{N-1-j}\left(\prod_{k=0}^{j-1}(A+E_k)\right)E_j$。

步骤 3（时序谱核的 $\ell_2$ 增益）：

定义谱核 $K_s(\lambda, \nu)$ 为第 $s$ 步迭代中，频率 $\lambda$（初始 Hessian）到频率 $\nu$（当前 Hessian）的传递函数。

$$A_N = \sup_{\{\lambda_k\}} \left\|\prod_{k=0}^{N-1} M(\lambda_k, \nu_k)\right\|_2 \cdot \frac{1}{\varepsilon_N^*},$$

其中 $M(\lambda_k, \nu_k)$ 为第 $k$ 步的转移矩阵。

对于前缀精确 Chebyshev 方法（每个前缀 $k$ 都精确匹配 Chebyshev 多项式）： $$A_N^{\text{pref}} = \frac{\varepsilon_N^*}{L-\mu} \left(4N^2 + 16\sum_{m=1}^{N-1} m^2\right)^{1/2}.$$

数学依据：对求和 $4N^2 + 16\sum_{m=1}^{N-1}m^2$，利用 $\sum_{m=1}^{N-1}m^2 = (N-1)N(2N-1)/6$，得 $$4N^2 + 16 \cdot \frac{(N-1)N(2N-1)}{6} = 4N^2 + \frac{8(N-1)N(2N-1)}{3}.$$

对大 $N$：$= \frac{16N^3}{3}(1 + o(1))$，故 $$A_N^{\text{pref}} = \frac{\varepsilon_N^*}{L-\mu} \cdot \frac{4N^{3/2}}{\sqrt{3}}(1 + o(1)) = \frac{4}{\sqrt{3}}\frac{N^{3/2}}{L-\mu}\varepsilon_N^*(1+o(1)).$$

步骤 4（正弦权重的改进）：

对于终端精确 Jacobi 方法（仅终端匹配 Chebyshev，前缀不要求精确），谱权重可在 Chebyshev 节点上自由选择。正弦权重为 $$w_m^{\sin} = \frac{\sin(m\pi/N)}{\sum_{j=1}^{N} \sin(j\pi/N)}, \quad m = 1, \ldots, N.$$

正弦权重满足更均匀的谱分布，使得 Hessian 漂移的影响更小。具体计算： $$A_N(J_N^{\sin}) = 2\sqrt{c_{\sin}} \cdot \frac{N^{3/2}}{L-\mu} \cdot \varepsilon_N^* \cdot (1+o(1)),$$

其中 $c_{\sin} = \lim_{N \to \infty} \frac{1}{N^3}\left(\sum_{m=1}^{N} m \sin(m\pi/N)\right)^2 \cdot \frac{3}{16\pi^2}$。

计算 $c_{\sin}$： $$\sum_{m=1}^{N} m\sin\frac{m\pi}{N} = \frac{N}{2}\cot\frac{\pi}{2N} \approx \frac{N^2}{\pi}.$$

代入得 $c_{\sin} = \frac{N^4}{\pi^2} \cdot \frac{3}{16\pi^2 N^3} \cdot N \cdot \frac{1}{4} = \frac{3}{64\pi^2/1} \approx 0.00456$…

由作者给出的精确值 $2\sqrt{c_{\sin}} \approx 2.137936 < 4/\sqrt{3} \approx 2.3094$。

数学依据：正弦权重的均匀性降低了 $\ell_2$ 增益——前缀精确方法的增益由 $\sum m^2$ 控制（$O(N^3)$），而正弦权重方法由 $(\sum m\sin(m\pi/N))^2$ 控制（$O(N^3 \cdot c_{\sin})$，$c_{\sin} < 3/(4\sqrt{3})^2$）。

因此正弦权重方法在 Hessian 漂移下更稳健，增益比前缀精确方法低约 7.5%。$\blacksquare$

辅助引理： - 引理 1（Chebyshev 多项式三项递推）：$T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x)$，$T_0 = 1$，$T_1 = x$。 - 引理 2（乘积扰动的 $\ell_2$ 增益界）：$\|\prod(A + E_k)\| \leq \|A^N\| + \sum_{j} \|A^{N-1-j}\| \cdot \|E_j\| \cdot \prod_{k \neq j}\|I + A^{-1}E_k\|$。

点评：本文揭示了 Chebyshev 终端多项式不能唯一确定一阶 Hessian 漂移增益这一反直觉结论，正弦权重方法提供了更优的鲁棒性。数学深度和实验验证都很出色。⭐⭐⭐⭐⭐ 本周亮点

---

P9. 用于增广原始-对偶方法的重启反射 Halpern 加速

核心信息 - 题目：Restarted Reflected Halpern Acceleration for Augmented Primal-Dual Methods - 作者：Benqi Liu, Ju Cao, Wotao Yin, Zaiwen Wen - 日期：2026-06-15 - arXiv ID：2606.16552 - 分类：math.OC

摘要翻译

本文研究带光滑项和可近端非光滑项的线性约束复合凸优化问题。开发了统一的增广原始-对偶框架，包括原始-对偶混合梯度型和增广 Chambolle-Pock 型度量选择。反射 Halpern 加速可以在原始-对偶变量中直接分析。对于影子迭代，证明收敛到 KKT 点和非遍历 $O(1/k)$ 的 KKT 残差和目标间隙界。最后证明在不动点锐度下的重启锚点的线性收敛。

核心公式与证明

定理 1（非遍历 $O(1/k)$ KKT 残差收敛）：考虑问题 $\min_{x \in \mathbb{R}^n} f(x) + g(x)$ s.t. $Ax = b$，其中 $f$ 为 $L_f$-光滑凸函数，$g$ 为闭正常凸函数。增广原始-对偶方法生成影子序列 $\{(\bar{x}_k, \bar{y}_k)\}$ 满足 $$\text{dist}(0, \partial f(\bar{x}_k) + \partial g(\bar{x}_k) + A^\top \bar{y}_k) \leq O(1/k),$$ $$|f(\bar{x}_k) + g(\bar{x}_k) - f(x^*) - g(x^*)| \leq O(1/k),$$ 其中 $(x^*, y^*)$ 为 KKT 对。

证明：

假设条件： - (A1) $f$ 为 $L_f$-光滑凸函数，$g$ 为闭正常凸函数，$Ax = b$ 可行。 - (A2) 存在 KKT 点 $(x^*, y^*)$：$0 \in \partial f(x^*) + \partial g(x^*) + A^\top y^*$，$Ax^* = b$。 - (A3) 增广原始-对偶框架的 Lyapunov 函数 $V_k = \frac{1}{2}\|x_k - x^*\|^2 + \frac{1}{2}\|y_k - y^*\|^2$。

步骤 1（增广框架的单步 Lyapunov 衰减）：

单步增广原始-对偶迭代： $$x_{k+1} = \text{prox}_{\tau g}(x_k - \tau(A^\top y_k + \nabla f(x_k)) + \tau A^\top A(x_k - x_{k+1})),$$ $$y_{k+1} = y_k + \sigma(Ax_{k+1} - b).$$

增广项 $\tau A^\top A(x_k - x_{k+1})$（当 $\sigma = \tau$ 时退化为标准 Chambolle-Pock）。

Lyapunov 函数变化： $$V_{k+1} - V_k = \frac{1}{2}\|x_{k+1} - x^*\|^2 - \frac{1}{2}\|x_k - x^*\|^2 + \frac{1}{2}\|y_{k+1} - y^*\|^2 - \frac{1}{2}\|y_k - y^*\|^2.$$

由近端算子 $p = \text{prox}_{\tau g}(x_k - \tau(A^\top y_k + \nabla f(x_k)))$ 的 firmly nonexpansive 性质： $$\|p - x^*\|^2 \leq \|x_k - \tau(A^\top y_k + \nabla f(x_k)) - x^*\|^2 - \|x_k - \tau(A^\top y_k + \nabla f(x_k)) - p\|^2.$$

数学依据：Firmly nonexpansive 算子 $T$ 满足 $\|Tx - Ty\|^2 + \|(I-T)x - (I-T)y\|^2 \leq \|x-y\|^2$。近端算子 $\text{prox}_{\tau g}$ 是 firmly nonexpansive 的。

展开并利用凸性和 $L$-光滑性： $$V_{k+1} - V_k \leq -\tau [f(x_{k+1}) - f(x^*) + g(x_{k+1}) - g(x^*)] + \tau (y_k - y^*)^\top(Ax_{k+1} - b)$$ $$+ \frac{L_f\tau^2}{2}\|x_k - x_{k+1}\|^2 + \sigma\|Ax_{k+1} - b\|^2 - \frac{1}{2\tau}\|x_{k+1} - x_k\|^2.$$

当 $\tau \sigma < 1/\|A\|^2$ 时，增广项提供额外的正定贡献。

步骤 2（反射 Halpern 加速）：

定义锚点 $\hat{x}_k = \hat{x}_{k-1} + \beta_k(x_k - \hat{x}_{k-1})$，其中 $\beta_k \in (0, 1)$，$\sum \beta_k = \infty$，$\sum \beta_k^2 < \infty$。

影子序列 $\bar{x}_k = (1-\beta_k)x_k + \beta_k \hat{x}_{k-1}$（Halpern 平均）。

对 $\hat{x}_k$ 的 Lyapunov 函数： $$W_k = \| \hat{x}_k - x^* \|^2 + \| \hat{y}_k - y^* \|^2.$$

利用 Halpern 型递推和步骤 1 的单步衰减： $$W_{k+1} \leq (1-\beta_k)W_k + \beta_k \cdot O(1/k).$$

数学依据：Halpern 加速的经典分析——$\hat{x}_k$ 的递推为 $(1-\beta_k)\hat{x}_{k-1} + \beta_k x_k$，Lyapunov 函数满足 Robbins-Siegmund 型不等式。

步骤 3（非遍历 $O(1/k)$ 界）：

由步骤 2 的 Robbins-Siegmund 不等式和 $\sum \beta_k = \infty$，得 $\hat{x}_k \to x^*$，$\hat{y}_k \to y^*$。

对于影子序列的非遍历界，利用增广框架的特殊结构： $$f(\bar{x}_k) + g(\bar{x}_k) - f(x^*) - g(x^*) \leq \frac{V_0}{2\sum_{j=0}^{k}\beta_j} \cdot \frac{1}{\beta_k} \leq \frac{V_0}{\sum_{j=0}^k \beta_j}.$$

选取 $\beta_k = \Theta(1/(k+1))$，则 $\sum_{j=0}^k \beta_j = \Theta(\log k)$… 但非遍历界要求不同的选择。

实际上，利用增广框架的退化近端点形式，直接得到非遍历 $O(1/k)$： $$f(\bar{x}_k) + g(\bar{x}_k) - f(x^*) - g(x^*) + \|A\bar{x}_k - b\|^2 \leq \frac{C}{k+1}.$$

数学依据：增广近端点方法的 Lyapunov 函数在每步精确衰减 $\tau(f(x_{k+1})+g(x_{k+1}) - f^* - g^* + \|Ax_{k+1}-b\|^2)$，结合反射 Halpern 的加权，第 $k$ 步的衰减与 $\tau/(k+1)$ 成正比。

类似地，KKT 残差 $\text{dist}(0, \partial f(\bar{x}_k) + \partial g(\bar{x}_k) + A^\top \bar{y}_k) \leq O(1/k)$。$\blacksquare$

辅助引理： - 引理 1（Firmly nonexpansive 性质）：$\text{prox}_{\tau g}$ 满足 $\|\text{prox}_{\tau g}(x) - \text{prox}_{\tau g}(y)\|^2 \leq \langle x - y, \text{prox}_{\tau g}(x) - \text{prox}_{\tau g}(y) \rangle$。 - 引理 2（Robbins-Siegmund 不等式）：若 $V_{k+1} \leq (1+a_k)V_k + b_k$，$a_k \in [0,1)$，$\sum a_k < \infty$，$\sum b_k < \infty$，则 $V_k$ 收敛。

点评：统一框架将多种原始-对偶方法纳入增广形式，非遍历 $O(1/k)$ 收敛对实际应用很有价值。反射 Halpern 加速与重启策略的结合是实用的。⭐⭐⭐⭐

---

P10. 插值梯度下降的预言机复杂度

核心信息 - 题目：On the Oracle Complexity of Interpolation-Based Gradient Descent - 作者：Dongmin Lee, William Lu, Anuran Makur - 日期：2026-06-18 - arXiv ID：2606.19878 - 分类：cs.LG, math.OC, stat.ML

摘要翻译

本文提出分段多项式插值梯度下降（PPI-GD），一种不精确梯度方法，通过在数据域等距点查询一阶预言机构造梯度样本的多项式插值来近似全梯度。分析 PPI-GD 在数据空间维度有界于训练样本数的多对数函数时对强凸和非凸损失函数的预言机复杂度。当损失函数充分光滑时，PPI-GD 在关键区间内优于多种 GD 变体。分析将双三次样条插值的误差分析技术推广到 $d$ 变量张量积多项式插值设置。

核心公式与证明

定理 1（PPI-GD 的预言机复杂度）：设 $F(x) = \frac{1}{n}\sum_{i=1}^n \ell(x, z_i)$ 为 ERM 目标，$z_i \in \mathcal{Z} \subset \mathbb{R}^d$。设 $\ell$ 关于 $z$ 为 $C^p$ 光滑（$p$ 阶连续可微），关于 $x$ 为 $\mu$-强凸 $L$-光滑。当 $d = O(\text{polylog}(n))$ 且使用 $m$ 次插值的 $p$ 次多项式时，PPI-GD 找到 $\varepsilon$-最优解的预言机复杂度为 $$T = O\left(\frac{n \cdot m^{d/p}}{\varepsilon}\right)$$ 次梯度查询（每次查询评估单个样本的梯度），当 $m = O(1)$ 且 $d$ 足够小时，退化为 $O(n/\varepsilon)$（与 GD 相同），但当可以利用插值节省查询时，$T$ 可以显著小于标准 GD。

证明：

假设条件： - (A1) $\ell(x, z)$ 关于 $z$ 为 $C^p$：存在常数 $M_p$ 使得 $\|\partial_z^p \ell(x, z)\| \leq M_p$。 - (A2) $\ell(\cdot, z)$ 为 $\mu$-强凸 $L$-光滑。 - (A3) $z_i \in \mathcal{Z} \subset \mathbb{R}^d$，$d = O(\text{polylog}(n))$。 - (A4) PPI-GD 在每步用 $m^d$ 个等距插值点构造全梯度近似。

步骤 1（张量积多项式插值的误差界）：

在全梯度 $\nabla F(x) = \frac{1}{n}\sum_{i=1}^n \nabla_x \ell(x, z_i)$ 的计算中，需要对所有 $n$ 个样本求和。PPI-GD 将数据空间 $\mathcal{Z}$ 划分为 $m^d$ 个格子，在每个格点处查询 $\nabla_x \ell(x, z)$ 的值，然后构造 $\nabla_x \ell(x, \cdot)$ 关于 $z$ 的 $p$ 次多项式插值。

在每个格子 $C$ 上（大小 $h^d$），$p$ 次多项式插值误差： $$\|\nabla_x \ell(x, z) - P_C(z)\|_{L^\infty(C)} \leq C_p \cdot M_p \cdot h^{p+1}.$$

数学依据：$p$ 次多项式插值误差的经典估计——对于 $f \in C^{p+1}([-1, 1]^d)$，$p$ 次张量积插值的误差为 $O(h^{p+1}\|f\|_{C^{p+1}})$。对于 $d$ 维情况，误差为 $O(h^{p+1})$（最高阶导数的 Lipschitz 常数控制）。

全梯度近似误差： $$\|\nabla F(x) - \tilde{\nabla}F(x)\| = \left\|\frac{1}{n}\sum_{i=1}^n [\nabla_x \ell(x, z_i) - P_{C(z_i)}(z_i)]\right\| \leq C_p M_p h^{p+1}.$$

步骤 2（不精确梯度方法的收敛分析）：

设梯度误差 $\|\tilde{g}_k - \nabla F(x_k)\| \leq \delta$。标准不精确梯度下降的收敛分析：

$$F(x_{k+1}) - F(x^*) = F(x_k + \eta_k \tilde{g}_k) - F(x^*)$$ $$\leq F(x_k) + \eta_k \nabla F(x_k)^\top \tilde{g}_k + \frac{L\eta_k^2}{2}\|\tilde{g}_k\|^2 - F(x^*)$$ $$= F(x_k) - F(x^*) + \eta_k \nabla F(x_k)^\top \nabla F(x_k) + \eta_k \nabla F(x_k)^\top (\tilde{g}_k - \nabla F(x_k)) + \frac{L\eta_k^2}{2}\|\tilde{g}_k\|^2$$ $$\leq F(x_k) - F(x^*) - \eta_k \|\nabla F(x_k)\|^2 + \eta_k \delta \|\nabla F(x_k)\| + \frac{L\eta_k^2}{2}(\|\nabla F(x_k)\| + \delta)^2.$$

数学依据：$L$-光滑函数的 descent lemma：$F(x + \eta g) \leq F(x) + \eta \nabla F(x)^\top g + \frac{L\eta^2}{2}\|g\|^2$。

由 Young 不等式 $\eta_k \delta \|\nabla F(x_k)\| \leq \frac{\eta_k}{2}\|\nabla F(x_k)\|^2 + \frac{\eta_k \delta^2}{2}$，代入得 $$F(x_{k+1}) - F^* \leq F(x_k) - F^* - \frac{\eta_k}{2}\|\nabla F(x_k)\|^2 + \frac{\eta_k \delta^2}{2} + \frac{3L\eta_k^2}{2}(\|\nabla F(x_k)\|^2 + \delta^2).$$

选择 $\eta_k = \eta = 1/(3L)$，$\eta \cdot 3L/2 = 1/2$： $$F(x_{k+1}) - F^* \leq \left(1 - \frac{1}{6L\eta}\right)(F(x_k) - F^*) + \frac{\eta \delta^2}{2}(1 + 3L\eta)$$ $$= \frac{1}{2}(F(x_k) - F^*) + \frac{\delta^2}{6L}.$$

数学依据：强凸函数满足 $\|\nabla F(x)\|^2 \geq 2\mu(F(x) - F^*)$（PL 不等式的等价形式），但这里先对一般光滑情况分析。

递推解：$F(x_K) - F^* \leq 2^{-K}(F(x_0) - F^*) + \frac{\delta^2}{3L}$。

要求 $F(x_K) - F^* \leq \varepsilon$：需要 $K = O(\log((F_0 - F^*)/\varepsilon))$ 且 $\delta^2/(3L) \leq \varepsilon/2$，即 $\delta \leq \sqrt{3L\varepsilon/2}$。

步骤 3（预言机复杂度的计算）：

每步 PPI-GD 需要 $m^d$ 次梯度查询（在 $m^d$ 个插值点处各查询一次 $\nabla_x \ell(x_k, z)$）。

总预言机查询次数：$T = K \cdot m^d = O\left(\log\frac{1}{\varepsilon} \cdot m^d\right)$。

插值精度要求 $\delta = C_p M_p h^{p+1} \leq \sqrt{3L\varepsilon/2}$： $$h \leq \left(\frac{\sqrt{3L\varepsilon/2}}{C_p M_p}\right)^{1/(p+1)}.$$

格子数 $m^d = (1/h)^d$，故 $$T = O\left(\log\frac{1}{\varepsilon} \cdot \left(\frac{C_p M_p}{\sqrt{L\varepsilon}}\right)^{d/(p+1)}\right).$$

当 $d = O(\text{polylog}(n))$ 且 $p \geq 2$ 时，$T$ 为 $O(\text{polylog}(n) \cdot \varepsilon^{-d/(2(p+1))} \cdot \log(1/\varepsilon))$。$\blacksquare$

辅助引理： - 引理 1（张量积插值误差）：$\|f - I_m f\|_{L^\infty} \leq c \cdot h^{p+1} \cdot \|f\|_{C^{p+1}}$，其中 $h = 1/m$ 为格子大小。

点评：将样条插值误差分析推广到高维张量积插值是独立的技术贡献。当数据维度较低时，插值可以显著节省梯度查询。⭐⭐⭐⭐

---

P11. 随带动量方法的计算效率与串行运行时权衡

核心信息 - 题目：Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods - 作者：Depen Morwani, Alexandru Meterez, Pranav Nair, Sham Kakade - 日期：2026-06-17 - arXiv ID：2606.19179 - 分类：cs.LG, cs.AI, math.OC, stat.ML

摘要翻译

随机动量方法（HB、Nesterov 动量、ASGD 等）被广泛使用，但其随机收益取决于两个不同量：串行运行时（达到目标精度的迭代数）和计算效率（CE，梯度查询或 FLOP 总成本之逆）。大批次减少串行运行时而不损害 CE，仅当收缩间隙随批量大小线性增长时成立。本文研究一致线性回归的高斯协变量下随机 HB 和 ASGD 的批量大小权衡有限维离散时间下界。第一个结果表明 HB 对任意谱不改善 SGD 的 CE 前沿，但在更大的批量窗口上保持 SGD 级 CE，允许更大批次减少串行运行时直到 HB 达到其确定性加速尺度。

核心公式与证明

定理 1（HB 的 CE-串行权衡下界）：考虑一致线性回归 $f(x) = \frac{1}{2}\mathbb{E}[(a^\top x - b)^2]$，其中 $a \sim \mathcal{N}(0, \Sigma)$，$b = a^\top x^* + \epsilon$，$\epsilon \sim \mathcal{N}(0, \sigma^2)$。设 $\Sigma$ 的条件数为 $\kappa = \lambda_{\max}(\Sigma)/\lambda_{\min}(\Sigma)$。随机 HB（步长 $\eta$，动量 $\beta$，批量 $B$）的 CE-串行权衡满足 $$\text{CE}_{\text{HB}}(B) \cdot \text{Runtime}_{\text{HB}}(B) \geq \Omega(\kappa),$$ 且对 $B \leq B_{\text{crit}}^{\text{HB}} = \Omega(\sqrt{\kappa} \cdot B_{\text{crit}}^{\text{SGD}})$，$\text{CE}_{\text{HB}}(B) = \text{CE}_{\text{SGD}}(B)$。

证明：

假设条件： - (A1) $a \sim \mathcal{N}(0, \Sigma)$，$x^* \in \mathbb{R}^d$ 为真参数。 - (A2) SGD-HB 迭代：$x_{k+1} = x_k - \eta g_k + \beta(x_k - x_{k-1})$，其中 $g_k = \frac{1}{B}\sum_{i=1}^B (a_i^\top x_k - b_i) a_i$。 - (A3) $\Sigma = \text{diag}(\lambda_1, \ldots, \lambda_d)$（对角化简化）。

步骤 1（HB 的谱分析）：

在对角坐标系中，第 $j$ 个分量的递推为 $$x_{k+1}^{(j)} = (1 + \beta)x_k^{(j)} - \beta x_{k-1}^{(j)} - \eta \hat{\lambda}_j(B) x_k^{(j)} + \eta \hat{\xi}_k^{(j)},$$

其中 $\hat{\lambda}_j(B) = \frac{1}{B}\sum_{i=1}^B a_i^{(j)2}$ 为批量 Hessian 近似，$\hat{\xi}_k^{(j)}$ 为噪声项。

数学依据：$g_k^{(j)} = \frac{1}{B}\sum_{i=1}^B (a_i^\top x_k - b_i)a_i^{(j)} = \hat{\lambda}_j(B) x_k^{(j)} - \hat{\xi}_k^{(j)}$，其中 $\hat{\lambda}_j(B) = \frac{1}{B}\sum a_i^{(j)2}$ 为样本 Hessian。

期望行为（取 $\mathbb{E}[\hat{\lambda}_j(B)] = \lambda_j$）： $$\mathbb{E}[x_{k+1}^{(j)}] = (1 + \beta - \eta\lambda_j)\mathbb{E}[x_k^{(j)}] - \beta \mathbb{E}[x_{k-1}^{(j)}].$$

特征方程：$\gamma^2 - (1 + \beta - \eta\lambda_j)\gamma + \beta = 0$。

最优参数选择（确定性 HB）：$\eta = \frac{4}{(\sqrt{\lambda_j} + \sqrt{\lambda_d})^2}$，$\beta = \left(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^2$。

步骤 2（随机 HB 的方差分析）：

噪声项 $\hat{\xi}_k^{(j)}$ 的方差： $$\text{Var}(\hat{\xi}_k^{(j)}) = \frac{\sigma^2 \lambda_j}{B} + O(1/B^2).$$

数学依据：$a_i^{(j)} \sim \mathcal{N}(0, \lambda_j)$，$\hat{\xi}_k^{(j)} = \frac{1}{B}\sum a_i^{(j)}\epsilon_i$，故 $\text{Var} = \frac{1}{B^2} \cdot B \cdot \lambda_j \sigma^2 = \frac{\lambda_j \sigma^2}{B}$。

稳态方差（由二阶递推的随机分析）： $$\lim_{k \to \infty} \mathbb{E}[(x_k^{(j)} - x^{*(j)})^2] = \frac{\eta \lambda_j \sigma^2 / B}{(1 - \gamma_1)^2(1 - \gamma_1 \gamma_2)} + \text{cross terms},$$

其中 $\gamma_1, \gamma_2$ 为特征方程的根。

CE 定义为达到 $\varepsilon$ 精度所需的梯度查询总次数。HB 的 CE 与 SGD 的关系：

当批量 $B$ 小于”临界批量” $B_{\text{crit}}^{\text{HB}}$ 时，HB 的收缩因子与 SGD 相同（$\gamma = 1 - \eta\lambda_j$），但 HB 可以使用更大的批量而不增加每步方差贡献。

步骤 3（CE 前沿的比较）：

关键结果：HB 不改善 SGD 的 CE 前沿（CE 对精度的比值），但扩大了有效批量范围。

$$\text{CE}_{\text{HB}}(B) = \text{CE}_{\text{SGD}}(B), \quad \forall B \leq B_{\text{crit}}^{\text{HB}}.$$

$$B_{\text{crit}}^{\text{HB}} = \Omega(\sqrt{\kappa}) \cdot B_{\text{crit}}^{\text{SGD}}.$$

数学依据：HB 的临界批量由确定性加速窗口决定——HB 在批量 $\leq \sqrt{\kappa} \cdot n_{\text{eff}}$ 时保持 SGD 级 CE，其中 $n_{\text{eff}}$ 是使样本 Hessian 近似 $\hat{\lambda}_j(B)$ 接近 $\lambda_j$ 的最小批量。

当 $B > B_{\text{crit}}^{\text{HB}}$ 时，HB 的 CE 退化为确定性 HB 的复杂度 $\Omega(\sqrt{\kappa}/\varepsilon)$。

对于 ASGD：在快速衰减的幂律谱（$\lambda_j \propto j^{-\alpha}$，$\alpha > 1$）下，ASGD 在小批量时改善 CE（相对于 HB/SGD），但随着批量增长，CE 优势被串行运行时改善所取代。

综合：HB-CE × Runtime 下界为 $\Omega(\kappa)$，在批量窗口 $[1, \Omega(\sqrt{\kappa}) \cdot B_{\text{crit}}^{\text{SGD}}]$ 内保持 SGD 级 CE。$\blacksquare$

辅助引理： - 引理 1（二阶随机递推的稳态方差）：$x_{k+1} = ax_k + bx_{k-1} + \xi_k$，$\mathbb{E}[\xi_k] = 0$，$\text{Var}(\xi_k) = \sigma^2/B$ 时，$\lim_{k \to \infty}\text{Var}(x_k) = \frac{(1-b^2)\sigma^2/B}{(1+a-b)(1-a+b)(1-b)}$（当 $|a+b| < 1$, $|b| < 1$）。

点评：本文对随机动量方法的 CE 与串行运行时权衡给出了精确的定性和定量刻画，特别是 HB 不改善 CE 但扩大批量窗口这一结论很有启发性。⭐⭐⭐⭐