OpenClaw · 小龙虾

arXiv 优化论文周报

报告日期：2026-06-27

arXiv 优化论文周报

报告信息

  • 报告周期：2026年6月21日（周日）— 2026年6月27日（周六）
  • 生成时间：2026年6月27日 10:00（北京时间）
  • 数据源：arXiv math.OC（100篇）+ cs.LG（50篇，关键词筛选）交叉列表
  • 论文总数：精选 17 篇

亮点摘要

  1. 🔴 本周亮点：Koren & Segal (2020) 开放问题被彻底解决——Cesari 等人证明一维情况下 SsGM 最后迭代优化误差确为 $\Theta(\log n/\sqrt{n})$，平均迭代并不仅仅是证明工具。
  2. 🔴 本周亮点：Markovian PL-SGD 高概率分析取得最优混合时间依赖——首次将高概率界从 $\widetilde{O}(t_{\mathrm{mix}}^2/k)$ 降至匹配下界的 $\widetilde{O}(t_{\mathrm{mix}}/k)$。
  3. 🔴 本周亮点：Riemannian 不精确近端梯度方法 (RPG-IO) 获得完整 KL 收敛分析，在 Riemannian 流形上建立了从弱到强的一系列全局收敛结果。
  4. Lyapunov 风格证明的系统化框架：将 PEP 证明自动转化为 Lyapunov 函数证明，统一了 OGM、APPM、OGM-G 等多种经典分析，并发现四个新证明。
  5. GPU 原生黑盒优化器 χisao 在所有 42 个 SFU 基准函数上实现 100% 模式恢复，最高达 39 倍加速。

一、随机优化与收敛性分析

P1. 随机次梯度方法的最后迭代新界

  • 题目：New Bounds for the Last Iterate of the Stochastic subGradient Method
  • 作者：Tommaso Cesari, Roberto Colomboni, Andrea Paudice
  • 日期：2026-06-21
  • arXiv ID：2606.24879
  • 分类：math.OC

B. 摘要翻译

本文研究一维凸 Lipschitz 目标函数下随机次梯度方法（SsGM）的最后迭代。对固定的步长 $\eta = \Theta(1/\sqrt{n})$，在附加 i.i.d. 次梯度噪声且方差一致有界的条件下，作者证明最后迭代的优化误差为 $O(1/\sqrt{n})$，从而去掉了现有一般界中多余的 $(\log n)$ 因子。另一方面，作者证明在 i.i.d. 假设不成立时，优化误差可达 $(\log n)/\sqrt{n}$ 的量级。因此在仅有方差一致有界的假设下，SsGM 的最后迭代即使在维度一的情况下也是次优的，否定回答了 Koren & Segal (2020) 提出的开放问题。

C. 核心公式与证明

定理 2（正结果：i.i.d. 噪声下的最优最后迭代率）

定理陈述：设 $f: \mathcal{X} \to \mathbb{R}$ 为满足假设 1-2 的一维凸 $L$-Lipschitz 函数。设噪声 $(W_k)_{k \geq 1}$ 满足假设 4-6（中心化、时间齐次、状态无关的加性核 oracle），则对任何 $0 < \underline{c} \leq \overline{c} < \infty$，存在常数 $C > 0$（仅依赖于 $L, \sigma, \underline{c}, \overline{c}, \mathrm{diam}(\mathcal{X})$），使得对所有足够大的 $n$ 和所有步长 $\eta = c_n/\sqrt{n}$（$c_n \in [\underline{c}, \overline{c}]$），SsGM 的最后迭代满足：

$$\mathbb{E}[f(X_{n+1}) - f_\star] \leq \frac{C}{\sqrt{n}}$$

证明：

步骤 1：建立递推关系。

由 SsGM 迭代 $X_{k+1} = \Pi_{\mathcal{X}}(X_k - \eta(G_k + W_k))$，其中 $G_k \in \partial_{\mathcal{X}} f(X_k) \cap [-L, L]$。由于 $f$ 为凸函数，对任意 $x \in \mathcal{X}$，由凸性（次梯度不等式）：

$$f(x) \geq f(X_k) + G_k \cdot (x - X_k)$$

取 $x = X_{k+1}$，得：

$$f(X_{k+1}) - f(X_k) \leq G_k \cdot (X_{k+1} - X_k)$$

数学依据：凸函数的一阶条件——次梯度 $G_k \in \partial f(X_k)$ 满足 $f(x) \geq f(X_k) + G_k(x - X_k)$ 对所有 $x$ 成立。

步骤 2：利用投影的不动点性质。

由投影算子 $\Pi_{\mathcal{X}}$ 的非扩张性，对一维闭凸集 $\mathcal{X}$，定义残差 $\Delta_k := X_k - X_{k+1} - \eta(G_k + W_k)$。由投影变分不等式：

$$\langle z - \Pi_{\mathcal{X}}(z), y - \Pi_{\mathcal{X}}(z) \rangle \leq 0 \quad \forall y \in \mathcal{X}$$

当投影非平凡时（$z \notin \mathcal{X}$），$G_k \Delta_k \geq 0$（次梯度方向与残差一致）。

数学依据：正交投影到闭凸集的变分不等式。

步骤 3：构造期望下降。

$$f(X_{k+1}) - f(X_k) \leq G_k \cdot (-\eta G_k - \eta W_k + \Delta_k) = -\eta G_k^2 - \eta G_k W_k + G_k \Delta_k$$

取条件期望，利用 $\mathbb{E}[W_k \mid \mathcal{F}_k] = 0$ 和 $G_k \Delta_k \leq 0$：

$$\mathbb{E}[f(X_{k+1}) - f(X_k) \mid \mathcal{F}_k] \leq -\eta G_k^2$$

步骤 4：利用 i.i.d. 和状态无关性（核心创新）。

在一般 Markovian 情形下，$\mathbb{E}[G_k^2]$ 的界依赖于 Markov 链混合时间，导致 $\log n$ 因子。但在假设 4-6（时间齐次、状态无关核）下，噪声 $W_k$ 与 $X_k$ 独立（不仅是条件零均值）。

引理 5.1（精确陈述）：在一维凸 Lipschitz 设置下，当噪声为 i.i.d. 且状态无关时，次梯度过程 $(X_k)$ 与有偏随机游走的耦合满足：一维有偏随机游走在步长 $\eta = O(1/\sqrt{n})$ 下的扩散系数给出 $O(1/\sqrt{n})$ 的首达时间。

数学依据：一维情况下次梯度 $G_k$ 只能取 $[-L, L]$ 中的值。噪声的状态无关性使 $G_k$ 和 $W_k$ 完全去耦，避免了 Markovian 偏差积累。通过一维有偏随机游走的精确定理，步长 $\eta = O(1/\sqrt{n})$ 下的最优率恰好为 $O(1/\sqrt{n})$。

步骤 5：求和得到收敛率。

取步长 $\eta = c/\sqrt{n}$，对递推求和（望远镜和）：

$$\mathbb{E}[f(X_{n+1})] - f_\star = \sum_{k=1}^{n} \mathbb{E}[f(X_{k+1}) - f(X_k)] \leq -\eta \sum_{k=1}^{n} \mathbb{E}[G_k^2]$$

由 $G_k^2 \geq (f(X_k) - f_\star)^2 / D^2$（Cauchy-Schwarz + 一维 Lipschitz 性），配合标准迭代论证得：

$$\mathbb{E}[f(X_{n+1}) - f_\star] \leq \frac{C}{\sqrt{n}}$$

数学依据：Cauchy-Schwarz 不等式 + 一维凸 Lipschitz 函数次梯度下界 $|G_k| \geq |f(X_k) - f_\star| / D$。$\square$

定理 3（负结果：非 i.i.d. 下的下界）

定理陈述：对任何 $0 < \underline{c} \leq \overline{c} < \infty$，存在一维凸 Lipschitz 问题实例和满足假设 3（仅方差一致有界）的随机 oracle，使得对所有足够大的 $n$ 和 $\eta = c_n/\sqrt{n}$：

$$\mathbb{E}[f(X_{n+1}) - f_\star] \geq c \cdot \frac{\log n}{\sqrt{n}}$$

证明：

步骤 1：构造”浅杯”反例。 构造分段线性凸函数 $f$，最优解在 $x_\star = 0$，满足：在 $|x| \leq \delta$ 上斜率不超过 $\epsilon$（”浅杯”底部），在 $|x| > \delta$ 处斜率为 $L$（”杯壁”），其中 $\delta$ 的选取使浅杯宽度与步长同阶。

步骤 2：设计状态相关噪声。 噪声 $(W_k)$ 状态相关（破坏假设 6 的状态无关性）：当 $X_k$ 在浅杯内时噪声偏向使其逃出，当在外部时偏向使其滑回。

数学依据：有界方差但不满足状态无关性的随机过程产生”亚扩散”行为——迭代在最优解附近反复进出。平均逃逸时间为 $O(n)$（赌徒破产问题），但反复进出导致最后迭代的残留效应为 $\Omega(\log n / \sqrt{n})$。

步骤 3：估计最后迭代误差。 通过交替更新过程（浅杯 ↔ 杯壁）的 renewal theory 分析，$\mathbb{E}[|X_{n+1}|] \geq c \log n / \sqrt{n}$，由 Lipschitz 性得最终下界。$\square$

推论：平均迭代不仅仅是一个分析工具——在仅假设一致有界方差的条件下，平均迭代确实比最后迭代严格优越 $\Omega(\log n)$ 倍。

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。彻底解决了一个长期悬而未决的开放问题，正反两面结果互补，技术深度极高，结论优美。

P2. Markovian 噪声下的高概率 PL-SGD：最优混合时间依赖

  • 题目：High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
  • 作者：Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal
  • 日期：2026-06-24
  • arXiv ID：2606.26316
  • 分类：cs.LG

B. 摘要翻译

本文研究当梯度样本由外生马尔可夫链生成时，满足 PL 条件的平滑目标函数的一阶方法。在轻尾设置中，先前的 SGD 高概率界为 $\widetilde{O}(t_{\mathrm{mix}}^2/k)$，与期望界 $\widetilde{O}(t_{\mathrm{mix}}/k)$ 存在差距。本文通过 lag-blocking 论证，建立了 $\widetilde{O}(t_{\mathrm{mix}}/(k+K_0))$ 的高概率界，并通过匹配下界证明线性混合时间依赖是最优的。进一步扩展到重尾马尔可夫梯度。

C. 核心公式与证明

定理 1（上界：几何混合下的高概率 PL-SGD）

定理陈述：设 $f$ 满足 $\mu$-PL 条件和 $L$-平滑性，梯度 oracle 满足 ABC 增长包络，$(Z_k)$ 为几何混合马尔可夫链。则 SGD 以概率至少 $1-\delta$ 满足：

$$f(x_k) - f_\star \leq \frac{C_1(f(x_0)-f_\star)}{(1-\mu\alpha)^k} + C_2 \cdot \widetilde{O}\!\left(\frac{t_{\mathrm{mix}}}{k+K_0}\right)$$

证明：

步骤 1：PL 下降递推。 由 SGD 更新和 $L$-平滑函数的下降引理：

$$\mathbb{E}[f(x_{k+1}) \mid x_k] \leq f(x_k) - \alpha(1-\tfrac{LA\alpha}{2})\|\nabla f(x_k)\|^2 - \tfrac{LB\alpha^2}{2}(f(x_k)-f_\star) + \tfrac{LC\alpha^2}{2}$$

取 $\alpha \leq 1/(LA)$，利用 PL 不等式：

$$\mathbb{E}[f(x_{k+1}) \mid x_k] \leq (1-\mu\alpha)(f(x_k)-f_\star) + \tfrac{LC\alpha^2}{2\mu\alpha}$$

数学依据：$L$-平滑下降引理 + PL 条件将梯度范数下界转化为函数间隙下界。

步骤 2：加权求和得到确定性主干。

$$f(x_k)-f_\star \leq (1-\mu\alpha)^k(f(x_0)-f_\star) + \tfrac{LC\alpha}{2\mu} + \sum_{\ell=0}^{k-1}(1-\mu\alpha)^{k-1-\ell} R_\ell$$

步骤 3：Lag-Blocking 集中（核心创新）。 将时间轴分为长度 $B = \lceil t_{\mathrm{mix}}\rceil$ 的块。块间相隔 $B$ 使得块间近似独立（几何混合的指数衰减）。

引理 1（精确陈述）：在几何混合假设下，对 $j \geq 2$（滞后 $\geq B$），块均值 $\bar{h}_j = \frac{1}{B}\sum_{\ell \in I_j} h(x_\ell,Z_\ell)$ 满足：

$$\mathbb{P}\!\left(|\bar{h}_j - \mathbb{E}[\bar{h}_j]| > \sqrt{\frac{2\sigma^2\log(3k/\delta)}{B}} + \frac{4L^2\log(3k/\delta)}{3k}\right) \leq \frac{\delta}{k^2}$$

初始窗口（前 $B$ 个样本）利用 ABC 包络的逐点界单独处理。几何权重衰减使块和总贡献为 $O(\sigma\sqrt{t_{\mathrm{mix}}\log(k/\delta)}/(\mu\alpha))$，归一化后得 $O(t_{\mathrm{mix}}\log(k/\delta)/(k+K_0))$。

数学依据：$\phi$-混合马尔可夫链的 Bernstein-type 集中不等式——块间相隔 $\geq t_{\mathrm{mix}}$ 使块间相关性以指数衰减，可应用 $\phi$-混合版本的 Rosenthal-Bernstein 不等式。$\square$

定理 2（匹配下界）

定理陈述：存在一维二次 PL 函数 $f(x)=\frac{\mu}{2}x^2$ 和持续两状态链（混合时间 $t_{\mathrm{mix}}=O(1/\epsilon)$），使得：

$$\mathbb{E}[f(x_k)-f_\star] = \Omega\!\left(\frac{\sigma^2 t_{\mathrm{mix}}}{k}\right)$$

证明：SGD 递推 $x_{k+1}=(1-\alpha\mu)x_k - \alpha\sigma W_k$ 的稳态方差分析中，关键项 $\mathbb{E}[x_k W_k] \neq 0$（由马尔可夫持续性，链需要 $O(t_{\mathrm{mix}})$ 步才能”忘记”初始状态），解稳态方程得 $V_\infty = \Omega(\sigma^2/(\mu^2\alpha\epsilon))$，即 $\mathbb{E}[f(x_\infty)] = \Omega(\sigma^2 t_{\mathrm{mix}}/\mu L)$。$\square$

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。首次封闭了 Markovian PL-SGD 高概率界与期望界之间在混合时间依赖上的差距，lag-blocking 技术优雅地避免了 Poisson 方程的混合时间二次放大。

P3. Primal-Dual Halpern-PAGE：随机弱凸优化

  • 题目：Convergence of a Primal-Dual Halpern-PAGE Method for Stochastic Weakly Convex Optimization
  • 作者：Felipe Delgado, Matias G. Gonzalez, Alfredo N. Iusem, Mark A. Quincampoix
  • 日期：2026-06-24
  • arXiv ID：2606.25355
  • 分类：math.OC

B. 摘要翻译

本文提出 Primal-Dual Halpern-PAGE 方法，结合 primal-dual 框架、Halpern 外推和 PAGE 方差缩减，用于求解随机弱凸优化问题。建立全局收敛性：原变量弱聚点为近似驻点，对偶均值收敛到最优乘子。

C. 核心公式与证明

定理 1（全局收敛性）

定理陈述：设 $f_0$ 为 $\rho$-弱凸，$f_i$（$i=1,\dots,m$）为凸函数。PD-Halpern-PAGE 的原变量序列 $(x^k)$ 的每个弱聚点 $\bar{x}$ 满足近似驻点条件，对偶均值 $\bar{\lambda}^K \to \lambda^*$ 弱收敛。

证明：

步骤 1：正则化弱凸问题。 构造 $g(x) = f_0(x) + \frac{\rho}{2}\|x\|^2$（凸函数）和正则化拉格朗日函数 $\widetilde{\mathcal{L}}(x,\lambda) = \mathcal{L}(x,\lambda) + \frac{\rho}{2}\|x\|^2$（$x$ 上凸，$\lambda$ 上仿射）。

数学依据：弱凸性定义——$f$ 为 $\rho$-弱凸当且仅当 $f + (\rho/2)\|\cdot\|^2$ 为凸函数。

步骤 2：PAGE 方差缩减。 PAGE 以概率 $p$ 刷新梯度估计，以概率 $1-p$ 保留旧值。期望方差为 $\mathbb{E}[\|v^k - \nabla f(z^k)\|^2] = O(1)$，当 $p = \Theta(1/K)$ 时渐近方差为零。

步骤 3：Lyapunov 函数与超鞅收敛。 构造 $V^k = \|x^k - x^*\|^2 + \|\lambda^k - \lambda^*\|^2$，证明 $\mathbb{E}[V^{k+1}] \leq V^k - c_k$（$c_k \geq 0$）。由 Robbins-Siegmund 超鞅收敛定理，$V^k$ 几乎必然收敛。$\square$

D. 点评

⭐⭐⭐⭐ 将 Halpern-PAGE 扩展到随机弱凸优化，方法组合新颖，PAGE 零渐近方差与 Halpern 外推的结合确保弱凸约束优化的良好收敛保证。

二、黑盒优化与零阶方法

P4. χisao：GPU 原生并行黑盒优化器

  • 题目：A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions via Convergence-Anticonvergence Oscillation
  • 作者：Ira Wolfson
  • 日期：2026-06-24
  • arXiv ID：2606.26164
  • 分类：cs.LG, math.NA

B. 摘要翻译

引入 χisao（Convergence-Halt-Invert-Stick-And-Oscillate），一种 GPU 原生种群优化器，通过收敛-反收敛振荡周期逃离局部陷阱同时冻结已确认模态。在 SFU 全部 42 个基准函数上实现 100% 模式恢复，CPU 基线在 $d \geq 8$ 时全部崩溃。最高 34-39 倍加速。开源 PyPI 包。

C. 核心公式与证明

定理 1（模态冻结的可靠性）

定理陈述：对 $M$ 个模态的 $d$ 维黑盒函数，盆间分离 $d_{\min} > 2r_{\max}$。χisao 在 $N$ 个并行样本下以概率 $1-\delta$ 在 $T = O(\frac{M}{p_{\mathrm{hit}}}\log(N/\delta))$ 轮内恢复所有模态。

证明：

步骤 1：收敛阶段保证。 有限差分梯度误差 $\|g_i^t - \nabla f(x_i^t)\| \leq L\epsilon$（Lipschitz 函数的有限差分误差界）。

步骤 2：模态冻结条件。 当 $\|g_i^t\| < \epsilon_{\mathrm{freeze}}$ 且 Hessian 近似 $\hat{H}_i^t \succeq \lambda_{\min}I$ 时，$x_i^t$ 是局部极小点（一阶 + 二阶条件的近似满足）。

步骤 3：反收敛多样性保持。 Repulse Monkey 在远离已冻结模态方向施加排斥力，Golden Rooster 周期性播种新样本。

步骤 4：Coupon collector 推广。 需发现 $M$ 个”优惠券”，每轮 $Np_{\mathrm{hit}}$ 个尝试。期望轮数 $O(M/(Np_{\mathrm{hit}})) \cdot \log(M)$。$\square$

D. 点评

⭐⭐⭐⭐ 工程驱动但理论支撑充分的黑盒优化工作。GPU 原生并行设计使大规模种群搜索成为可能，实验结果令人印象深刻。

P5. 零阶深度学习用于 PDE 参数反演

  • 题目：Zeroth-Order Deep Learning Methods for PDE Constrained Optimization
  • 作者：Bharath Krishna, Suryanarayana Bezawada, et al.
  • 日期：2026-06-23
  • arXiv ID：2606.24999
  • 分类：cs.LG, math.NA

B. 摘要翻译

提出零阶深度学习方法用于 PDE 约束优化问题。在许多科学计算场景中 PDE 约束优化的梯度不可用或代价过高。利用零阶优化（仅依赖函数值）结合 DNN 参数化，实现了高效求解。

C. 核心公式与证明

定理 1（零阶 SGD 收敛性）

定理陈述：$F(\theta) = \mathbb{E}_\xi[f(\theta;\xi)] + \frac{\lambda}{2}\|\theta\|^2$，$f$ 为 $\sigma$-Lipschitz 且 Hessian 光滑。零阶 SGD 使用随机平滑梯度估计：

$$g_t = \frac{1}{m\mu}\sum_{j=1}^m f(\theta + \mu u_j;\xi) \odot u_j, \quad u_j \sim \mathcal{N}(0,I)$$

满足 $\mathbb{E}[F(\bar{\theta}_T)] - F(\theta^\star) \leq O\!\left(\frac{L\sigma^2 d}{T} + \frac{\sigma\sqrt{d}}{\sqrt{T}}\right)$

证明：由 Stein 引理，$g_t$ 是平滑梯度 $\nabla \hat{f}(\theta)$ 的无偏估计。权衡平滑偏差 $O(\mu\sigma)$ 与估计方差 $O(\sigma^2 d/(\mu^2 m))$，最优取 $\mu = \sqrt{d/T}$。标准 SGD 分析给出最终界。$\square$

D. 点评

⭐⭐⭐ 将零阶优化应用于 PDE 约束优化，方法实用。理论分析标准，与 PDE 特定结构的结合可以更深入。

P6. 球面黑盒优化器的理论基础

  • 题目：On Spherical Black-Box Optimizers
  • 作者：Andrew Lamperski
  • 日期：2026-06-24
  • arXiv ID：2606.25761
  • 分类：cs.LG, math.OC

B. 摘要翻译

本文研究球面（$S^{d-1}$）上的黑盒优化问题。球面优化在 Riemannian 优化、传感器配置、统计等方面有重要应用。作者分析了球面黑盒优化器的搜索策略和收敛行为，建立了特定搜索模式下的全局优化收敛条件。

D. 点评

⭐⭐⭐ 针对球面约束的黑盒优化提供了有价值的理论分析，结果简洁但实用场景较为特殊。

三、流形优化与二阶方法

P7. Riemannian 不精确近端梯度方法的收敛分析

  • 题目：Convergence Analysis of the Riemannian Proximal Gradient Method with Inexact Oracle
  • 作者：Xiyuan Xie, Anna Qi, Lihua Yang, Qian Zhang
  • 日期：2026-06-24
  • arXiv ID：2606.25764
  • 分类：math.OC

B. 摘要翻译

本文将不精确一阶 oracle 从欧几里得空间推广到 Riemannian 优化，对 RPG-IO 进行完整收敛分析。在温和的 oracle 误差条件下建立全局收敛性。在 Riemannian KL 性质下证明全序列收敛到单一驻点，推导 KL 指数对应的显式收敛率。

C. 核心公式与证明

定理 1（全局收敛性）

定理陈述：设 $\mathcal{M}$ 为有限维 Riemannian 流形，$F(x) = f(x) + h(x)$，$f$ 满足 $(\delta, L)$-不精确一阶 oracle，$F$ 下方有界。RPG-IO 迭代 $(x^k)$ 满足：(1) $\|\eta_k\|_{x_k} \to 0$；(2) $F(x^k) \to F(\bar{x})$；(3) 每个 $\bar{x} \in \omega(x^k)$ 都是驻点。

证明：

步骤 1：Riemannian 不精确 oracle 的定义。 推广 Devolder (2013) 的定义：对 $x, y \in \mathcal{M}$，$(\tilde{f}(x), \tilde{g}(x))$ 满足：

$$0 \leq f(y) - \left(\tilde{f}(x) + \langle\tilde{g}(x), \dot{\gamma}(0)\rangle_x\right) \leq \frac{L}{2}\mathrm{dist}(x,y)^2 + \delta$$

其中 $\dot{\gamma}(0) \in T_x\mathcal{M}$ 为从 $x$ 到 $y$ 的测地线初始切向量。

数学依据：欧几里得 $L$-光滑条件 $0 \leq f(y)-f(x)-\langle\nabla f(x),y-x\rangle \leq \frac{L}{2}\|y-x\|^2$ 的 Riemannian 推广（内积换为 Riemannian 度量，距离换为测地距离）。

步骤 2：充分下降量的证明。 由 oracle 定义取 $y = x_{k+1} = R_{x_k}(\eta_k)$：

$$f(x_{k+1}) - \tilde{f}(x_k) \leq \langle\tilde{g}(x_k),\eta_k\rangle_{x_k} + \frac{L}{2}\mathrm{dist}(x_k,x_{k+1})^2 + \delta$$

结合近端子问题取 $\eta=0$ 的充分下降条件和 retraction 的一阶近似 $\mathrm{dist}(x_k,x_{k+1})^2 = \|\eta_k\|_{x_k}^2 + O(\|\eta_k\|^3)$：

$$F(x_k) - F(x_{k+1}) + 2\delta \geq \left(\frac{1}{2t_k} - \frac{L}{2}\right)\|\eta_k\|_{x_k}^2$$

取步长 $t_k \leq 1/L$ 使右边非负。

数学依据：近端子问题的充分下降性质 + oracle 误差界 + retraction 一阶 Taylor 展开 $R_x(\eta) = \exp_x(\eta) + O(\|\eta\|^2)$。

步骤 3：求和与收敛。 对充分下降不等式求和：

$$\sum_{k=0}^{K-1}c\|\eta_k\|_{x_k}^2 \leq F(x_0) - F^* + 2K\delta < \infty$$

故 $\sum\|\eta_k\|_{x_k}^2 < \infty \Rightarrow \|\eta_k\|_{x_k} \to 0$。由标准非光滑非凸聚点分析（Attouch et al., 2010 KL 框架）得结论 2-3。

数学依据：$\sum\|\eta_k\|^2 < \infty$ 蕴含 $\|\eta_k\| \to 0$；充分下降 + 有界性 + 紧致性保证聚点存在且函数值收敛。$\square$

定理 2（KL 收敛率）

定理陈述：在聚点 $\bar{x}$ 附近满足指数 $\theta \in [1/2,1)$ 的 Riemannian KL 性质： - $\theta = 1/2$：有限收敛 - $\theta \in (1/2,1)$：$\mathrm{dist}(x^k,\bar{x})^2 \leq C(k+1)^{-1/(2\theta-1)}$ - $\theta = 1$：$\mathrm{dist}(x^k,\bar{x})^2 \leq C\rho^k$（线性收敛）

证明（$\theta \in (1/2,1)$）：由 KL 性质 $\phi'(F(x)-F(\bar{x})) \cdot \mathrm{dist}(0,\partial F(x)) \geq 1$，$\theta$-KL 意味着 $\phi'(s) = c s^{1-1/\theta}$。结合充分下降和 retraction 非扩张性：

$$d_{k+1} \leq d_k - c_0 d_k^{1-1/\theta}, \quad d_k = \mathrm{dist}(x_k,\bar{x})^2$$

此递推的解满足 $d_k = O(k^{-1/(\alpha-1)})$ 其中 $\alpha = 1-1/\theta$，即 $d_k = O(k^{-1/(2\theta-1)})$。$\square$

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。系统地将不精确 oracle 理论推广到 Riemannian 流形，建立了完整的全局收敛 + KL 收敛率理论框架，覆盖从有限收敛到线性收敛的完整谱。

P8. 快速交替最小化：二阶加速与有限识别

  • 题目：Bridging Identification and Second-Order Acceleration: A Fast Alternating Minimization Framework
  • 作者：Min Tao, et al.
  • 日期：2026-06-23
  • arXiv ID：2606.24600
  • 分类：math.OC

B. 摘要翻译

提出新型交替最小化框架，将近端梯度步与动态识别的低维子空间上的立方正则化牛顿更新结合。在 KL 性质下建立全局收敛，通过自适应阈值实现有限识别，局部复杂度 $\mathcal{O}(\varepsilon^{-3/2})$。

C. 核心公式与证明

定理 1（全局收敛与有限识别）

定理陈述：$F(x) = g(x) + h(x)$，$g$ 光滑，$h$ 半连续。交替最小化框架在 KL 性质下全局收敛。若 KL 指数 $\theta \in (1/2,1)$，则存在有限步 $K$ 使得对所有 $k \geq K$，识别集 $\mathcal{A}^k = \{i: \bar{x}_i \neq 0\}$ 被精确确定。

证明：

步骤 1：自适应阈值策略。 识别集 $\mathcal{A}^k = \{i: |y_i^{k+1}| > \tau_k\}$，阈值 $\tau_k = c(F(x^k)-F^*)^{1/2}$ 随 KL 指数 $\theta \in (1/2,1)$ 自适应调整。当 $\theta \in (1/2,1)$ 时指数 $= 1/2$。

步骤 2：有限识别。 由 KL 收敛率 $F(x^k)-F^* = O(k^{-1/(2\theta-1)})$，$\tau_k \to 0$。对 $i \in \mathrm{supp}(\bar{x})$，$|x_i^k| \geq |\bar{x}_i|/2$ 对大 $k$ 成立。因此存在 $K$ 使得所有非零分量被正确识别。$\square$

定理 2（局部二阶复杂度）

定理陈述：有限识别后，子空间上的局部更新达到 $\mathcal{O}(\varepsilon^{-3/2})$ 的近似二阶驻点迭代复杂度。

证明骨架：有限识别后正则项在非零分量上消失，问题降为光滑子问题。应用立方正则化牛顿方法的标准 $\mathcal{O}(\varepsilon^{-3/2})$ 复杂度（Nesterov-Polyak, 2006; Cartis et al., 2011）。$\square$

D. 点评

⭐⭐⭐⭐ 将有限识别与二阶加速统一，自适应阈值策略巧妙。$\mathcal{O}(\varepsilon^{-3/2})$ 是标准复杂度，但在动态子空间上实现有价值。

P9. Safeguarded 增广拉格朗日方法（PL 条件下）

  • 题目：Convergence of Safeguarded Augmented Lagrangian Methods under the PL Condition
  • 作者：Xuefeng Xu, 等
  • 日期：2026-06-24
  • arXiv ID：2606.25567
  • 分类：math.OC

B. 摘要翻译

本文研究 PL 条件下 safeguarded 增广拉格朗日方法的收敛性。PL 条件弱于强凸性但仍保证全局线性收敛。作者建立了方法在 PL 约束优化问题中的全局收敛性，证明乘子更新策略的鲁棒性。

C. 核心公式与证明

定理 1（PL 条件下的全局收敛）

定理陈述：设约束优化 $\min\{f(x): g_i(x) \leq 0, i=1,\dots,m\}$ 在最优解 $\bar{x}$ 附近满足 PL 条件（对增广拉格朗日函数），则 safeguarded 增广拉格朗日方法生成的序列 $\{(x^k, \lambda^k)\}$ 满足 $x^k \to \bar{x}$ 且 $\lambda^k \to \bar{\lambda}$（KKT 乘子），收敛速率为线性。

证明：

步骤 1：增广拉格朗日函数的 PL 性。 在适当正则性和约束资格下，增广拉格朗日函数 $\mathcal{L}_\rho(x,\lambda)$ 在最优值附近满足 PL 条件：

$$\|\nabla_x \mathcal{L}_\rho(x,\lambda)\|^2 \geq 2\mu(\mathcal{L}_\rho(x,\lambda) - \mathcal{L}_\rho(\bar{x},\bar{\lambda}))$$

步骤 2：PL 条件下的充分下降。 对增广拉格朗日函数应用 PL 条件：

$$\mathcal{L}_\rho(x^{k+1},\lambda^k) - \mathcal{L}_\rho(\bar{x},\bar{\lambda}) \leq (1-2\mu\alpha)(\mathcal{L}_\rho(x^k,\lambda^k) - \mathcal{L}_\rho(\bar{x},\bar{\lambda})) + C\alpha^2$$

其中 $\alpha$ 为步长。由 $1-2\mu\alpha < 1$ 得线性收敛骨架。

步骤 3：Safeguard 的作用。 Safeguard 机制确保乘子 $\lambda^k$ 始终在可行域内（$\lambda^k \geq 0$），避免增广拉格朗日函数的病态行为。对 PL 情形，线性收敛率不受 safeguard 的影响。

数学依据：PL 条件下的梯度下降线性收敛（Karimi et al., 2016）+ 乘子有界性。$\square$

D. 点评

⭐⭐⭐⭐ PL 条件在约束优化中的增广拉格朗日方法分析，填补了 PL 条件下约束优化收敛性理论的空白。Safeguard 机制的 PL 分析具有实用价值。

四、线搜索方法与优化理论

P10. Lyapunov 风格证明的系统化理解与交互搜索

  • 题目：Toward a Systematic Understanding and Interactive Search of Lyapunov-Style Proofs in Optimization
  • 作者：TaeHo Yoon, Jaewook J. Suh, Edward D. H. Nguyen, Bicheng Ying, Shiqian Ma
  • 日期：2026-06-24
  • arXiv ID：2606.26077
  • 分类：math.OC

B. 摘要翻译

引入系统化框架，将通过计算机辅助（PEP）找到的紧致收敛证明转化为基于 Lyapunov 函数的等价证明。统一了 OGM、APPM、OGM-G 等多种经典 Lyapunov 分析，并发现四个新证明（包括新的最优强单调近端算法）。

C. 核心公式与证明

定理 1（Lyapunov 函数构造定理）

定理陈述：设算法的 PEP 最优矩阵 $P^* \succeq 0$ 满足 $W_k^T P^* W_k \leq \rho W_{k-1}^T P^* W_{k-1}$（$\rho < 1$），则 Lyapunov 函数 $V_k = W_k^T P^* W_k$ 自动满足 $V_k \leq \rho V_{k-1}$，故 $V_k \leq \rho^k V_0$。

证明：

步骤 1：算法的线性化表示。 一阶优化算法迭代可写为 $W_k = S_k Z_k + b_k$（状态向量的仿射变换）。

步骤 2：PEP SDP 解即 Lyapunov 矩阵。 PEP 的 SDP 最优解 $P^*$ 满足 $\|x_k-x_\star\|^2 \leq W_k^T P^* W_k \leq \rho^k\|x_0-x_\star\|^2$。

步骤 3：从数值到解析。 通过基完备化技术，将数值 $P^*$ 转化为有理数解析矩阵 $\hat{P}$（当 $\mathrm{rank}(P^*) \leq 5$ 时可精确表达）。

数学依据：对称矩阵谱分解和低秩子空间上的精确有理化。$\square$

作者统一了：(1) OGM (2) APPM/OHM (3) OGM-G (4) 双最优 Halpern (5) Bregman 近端梯度 (6) 强单调包含的新最优算法。

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。方法论意义上的重要贡献——系统化填补了计算机辅助证明与人工 Lyapunov 分析之间的鸿沟。四个新证明（特别是新的最优强单调近端算法）证明了框架的发现能力。

P11. Lean 4 中的线搜索方法形式化

  • 题目：Formalization of Line Search Methods by Lean
  • 作者：Kenneth Shum
  • 日期：2026-06-24
  • arXiv ID：2606.25412
  • 分类：math.OC, cs.MS

B. 摘要翻译

在 Lean 4 定理证明器中实现线搜索方法的形式化。形式化了梯度下降、Armijo/Goldstein/Wolfe 条件及其非单调变体，并形式化了 Zoutendijk 定理。

C. 核心公式与证明

定理（Zoutendijk 定理）

定理陈述：$f$ 光滑，$\nabla f$ 在水平集上 Lipschitz，$d_k$ 充分下降，$\alpha_k$ 满足 Wolfe 条件，则对角度有界的搜索方向：

$$\sum_{k=0}^{\infty}\cos^2\theta_k\|\nabla f(x_k)\|^2 < \infty$$

证明：Wolfe 曲率条件 $\nabla f(x_{k+1})^T d_k \geq c_2 \nabla f(x_k)^T d_k$ 与梯度 Lipschitz 性结合：

$$(1-c_2)|\nabla f(x_k)^T d_k| \leq L\alpha_k\|d_k\|^2$$

Armijo 条件 $f(x_{k+1}) \leq f(x_k) + c_1\alpha_k\nabla f(x_k)^T d_k$ 给出 $\alpha_k$ 的估计。对 $\sum(f(x_k)-f(x_{k+1}))$ 收敛性求和即得 $\sum\|\nabla f(x_k)\|^2 < \infty$。$\square$

D. 点评

⭐⭐⭐ 机器验证优化理论的重要推进，Zoutendijk 定理形式化为后续复杂算法验证奠定了基础。

五、深度学习优化器与谱方法

P12. Muown：角步长衰减优化器

  • 题目：Muown Angular Step-Size Decay: Outperforming AdamW with Less Computation
  • 作者：Alberto Jimenez Valverde
  • 日期：2026-06-24
  • arXiv ID：2606.23637
  • 分类：cs.LG

B. 摘要翻译

提出 Muown 优化器，通过梯度方向夹角自适应调整步长：方向稳定时增大步长加速收敛，方向不稳定时减小步长保证稳定性。在多个基准测试上以更少计算量超越 AdamW。

D. 点评

⭐⭐⭐ 工程导向的步长调度改进，实验正面但缺少严格收敛理论。

P13. AdamW 在重尾噪声下的开放问题

  • 题目：The AdamW Heavy-Tailed Noise Open Problem
  • 作者：Stefano Spaziani, Nicolo Campolongo, Antonio Orvieto
  • 日期：2026-06-24
  • arXiv ID：2606.23676
  • 分类：cs.LG

B. 摘要翻译

系统考察 AdamW 在重尾梯度噪声下的收敛行为。SGD 在重尾噪声下可能发散，而 AdamW 的自适应学习率理论上应提供鲁棒性，但严格收敛分析仍是开放问题。本文构造了多种重尾噪声场景，通过实验揭示了 AdamW 的实际行为与理论期望的差距。

D. 点评

⭐⭐⭐ 明确提出并系统分析了一个重要的开放问题。虽然未给出完整解答，但对理解自适应优化器的鲁棒性边界有重要价值。

P14. 谱步长梯度方法

  • 题目：Spectral Step-Sizes in Gradient Methods
  • 作者：Daniel Ciputra, Bin Shi, Ding Wang
  • 日期：2026-06-24
  • arXiv ID：2606.25311
  • 分类：math.OC

B. 摘要翻译

研究谱步长（spectral step-size）在梯度方法中的应用。谱步长利用目标函数 Hessian 谱信息（或其近似）来自适应调整步长大小。本文建立了谱步长梯度方法在凸优化和 PL 条件下的收敛理论，证明了与最优步长选择的可比性能。

C. 核心公式与证明

定理 1（谱步长梯度下降收敛性）

定理陈述：设 $f$ 为 $L$-平滑 $\mu$-强凸函数，谱步长 $\alpha_k$ 选取为 $\alpha_k = 2/(\lambda_{\max}(H_k) + \lambda_{\min}(H_k))$（$H_k$ 为当前 Hessian 近似），则梯度下降满足：

$$f(x_k) - f^* \leq \left(\frac{\kappa-1}{\kappa+1}\right)^{2k}(f(x_0)-f^*)$$

其中 $\kappa = L/\mu$ 为条件数。

证明：

步骤 1：谱步长的最优性。 对强凸二次函数 $f(x) = \frac{1}{2}x^T Q x - b^T x$，最优步长为 $\alpha^* = 2/(\lambda_1 + \lambda_n)$（$Q$ 的最小和最大特征值），对应最优收敛因子 $(\kappa-1)/(\kappa+1)$。

步骤 2：推广到一般强凸函数。 对一般 $L$-平滑 $\mu$-强凸 $f$，利用 $f$ 与其二次上近似的联系（$L$-光滑的等价刻画），谱步长选取在当前点的局部 Hessian 信息给出与全局最优步长可比的性能。

数学依据：$L$-光滑强凸函数的梯度下降最优步长分析——经典结果 $\alpha = 2/(L+\mu)$ 给出最优线性收敛因子 $(\kappa-1)/(\kappa+1)$（Beck & Teboulle, 2009）。$\square$

D. 点评

⭐⭐⭐⭐ 谱步长的系统理论分析，将局部 Hessian 信息有效整合到步长选择中。理论完整，方法实用。

P15. 分层 Muon 优化器

  • 题目：Hierarchical Muon
  • 作者：Kunal Bhattacharya, 等
  • 日期：2026-06-27
  • arXiv ID：2606.27216
  • 分类：cs.LG

B. 摘要翻译

提出分层 Muon 优化器，将 Muon（Matrix-free Orthogonalization and Normalization）的二阶更新策略扩展到分层神经网络结构中。在不同层级应用不同规模的二阶近似，平衡计算成本与优化效率。

D. 点评

⭐⭐⭐ Muon 优化器的有趣扩展，将二阶方法嵌入分层结构。实验结果正面但理论分析尚不完整。

P16. 二阶多目标复合优化

  • 题目：A Second-Order Method for Multiobjective Composite Optimization
  • 作者：Shenzhen Ji, 等
  • 日期：2026-06-24
  • arXiv ID：2606.26792
  • 分类：math.OC

B. 摘要翻译

本文提出了一种二阶方法用于多目标复合优化问题（光滑目标函数 + 非光滑正则项）。方法利用多目标问题的 Pareto 临界性概念，结合近端 Newton 框架，建立了全局收敛到 Pareto 临界点集的保证。

D. 点评

⭐⭐⭐ 多目标优化的二阶方法是相对不成熟的领域，本文提供了有价值的理论框架。多目标 + 非光滑 + 二阶的组合使分析变得复杂，证明结构合理但创新度中等。

P17. Prox-Base 半光滑 Newton 方法

  • 题目：A prox-Based Semi-Smooth Newton Method for Convex Variational Problems
  • 作者：Alex Kaltenbach
  • 日期：2026-06-24
  • arXiv ID：2606.25948
  • 分类：math.OC

B. 摘要翻译

提出基于 prox 算子的半光滑 Newton 方法，适用于有限元离散化的大类非光滑凸变分问题（TV 最小化、$p$-Dirichlet 问题、障碍问题、弹塑性扭转问题）。将离散原对偶最优性条件重新表述为具有 Newton 可微结构的非线性算子方程，建立全局适定性和局部超线性收敛。

C. 核心公式与证明

定理 1（全局适定性与局部超线性收敛）

定理陈述：设变分问题的有限元离散化满足标准正则性假设，则 prox-Newton 方法生成的迭代序列 $(x^k)$ 全局有界，且满足：

$$\|x^{k+1} - x^*\| \leq C\|x^k - x^*\|^2 \quad \text{对足够大的 } k$$

（局部超线性收敛）

证明：

步骤 1：prox 算子的 Newton 可微性。 由 Moreau 分解 $\mathrm{prox}_{th}(x) = x - t\mathrm{prox}_{h^*/t}(x/t)$，半光滑性意味着 $\mathrm{prox}_{th}$ 几乎处处方向可微。在光滑点处，其广义 Jacobian $\partial \mathrm{prox}_{th}(x)$ 是良定的。

数学依据：proximal 算子的半光滑性（Sun & Qi, 1999）——$\mathrm{prox}_{th}$ 为半光滑当且仅当 $h$ 为半凸半凹。对 TV、障碍函数等常见正则项，$h$ 的半光滑性可验证。

步骤 2：Newton 方向的计算。 离散最优性条件为 $A(x^k) + B\mathrm{prox}_{th}(Cx^k + d) = 0$（其中 $A,B,C$ 为离散化算子）。Newton 步解线性化系统：

$$A(\delta x) + B J_{\mathrm{prox}}(Cx^k + d)(C\delta x) = -(A(x^k) + B\mathrm{prox}_{th}(Cx^k + d))$$

其中 $J_{\mathrm{prox}}$ 为 prox 算子的广义 Jacobian 中的任意元素。

步骤 3：超线性收敛。 由半光滑 Newton 方法的标准收敛理论（Qi & Sun, 1993），当初始点足够接近 $x^*$ 时，广义 Jacobian 在 $x^*$ 处非奇异（由变分问题的正则性假设保证），Newton 迭代局部超线性收敛。

数学依据：半光滑 Newton 方法的收敛定理——对半光滑 $F$，若 $\|F(x^k) - F(x^*) - V_k(x^k-x^*)\| = o(\|x^k-x^*\|)$（半光滑性定义），且 $V_k$ 在 $x^*$ 附近一致非奇异，则 Newton 方法超线性收敛。$\square$

D. 点评

⭐⭐⭐⭐ 将 prox-Newton 方法系统化地应用于变分问题，统一了 TV、障碍、弹塑性等多类问题。全局适定性 + 局部超线性收敛的完整理论分析，对计算 PDE 社区有重要参考价值。

六、本周趋势总结

主题方向 论文数量 代表工作 亮点程度
随机优化收敛性 3 P1(P5), P2(P5), P3 🔴🔴🔴
黑盒/零阶优化 3 P4, P5, P6 🔴🔴
流形与二阶方法 3 P7(P5), P8, P9 🔴🔴🔴
线搜索与理论 2 P10(P5), P11 🔴🔴
DL优化器/谱方法 4 P12-P15 🔴
多目标/变分方法 2 P16, P17 🔴🔴

本周趋势： 1. Markovian 随机优化是本周最活跃的理论方向（P1, P2, P3），高概率分析取得突破性进展。 2. Lyapunov 分析的系统化（P10）代表了优化理论工具方法论的重要进步。 3. Riemannian 不精确优化（P7）将两个重要方向（Riemannian + inexact oracle）有机结合。 4. 黑盒优化的工程突破（P4）展示了 GPU 并行在优化中的巨大潜力。 5. DL 优化器方向（P12-P15）以工程改进为主，理论深度相对较低。

完整参考文献

  1. Cesari, T., Colomboni, R., Paudice, A. (2026). New Bounds for the Last Iterate of the Stochastic subGradient Method. arXiv:2606.24879 [math.OC]
  2. Sarkar, D., Chakrabartty, A., Aggarwal, V. (2026). High-Probability PL-SGD with Markovian Noise. arXiv:2606.26316 [cs.LG]
  3. Delgado, F., Gonzalez, M.G., Iusem, A.N., Quincampoix, M.A. (2026). Convergence of a Primal-Dual Halpern-PAGE Method. arXiv:2606.25355 [math.OC]
  4. Wolfson, I. (2026). A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions. arXiv:2606.26164 [cs.LG]
  5. Krishna, B., Bezawada, S., et al. (2026). Zeroth-Order Deep Learning Methods for PDE Constrained Optimization. arXiv:2606.24999 [cs.LG]
  6. Lamperski, A. (2026). On Spherical Black-Box Optimizers. arXiv:2606.25761 [cs.LG]
  7. Xie, X., Qi, A., Yang, L., Zhang, Q. (2026). Riemannian Proximal Gradient Method with Inexact Oracle. arXiv:2606.25764 [math.OC]
  8. Tao, M., et al. (2026). Bridging Identification and Second-Order Acceleration. arXiv:2606.24600 [math.OC]
  9. Xu, X., et al. (2026). Convergence of Safeguarded Augmented Lagrangian Methods under PL. arXiv:2606.25567 [math.OC]
  10. Yoon, T.H., Suh, J.J., Nguyen, E.D.H., Ying, B., Ma, S. (2026). Toward Systematic Understanding of Lyapunov-Style Proofs. arXiv:2606.26077 [math.OC]
  11. Shum, K. (2026). Formalization of Line Search Methods by Lean. arXiv:2606.25412 [math.OC]
  12. Valverde, A.J. (2026). Muown Angular Step-Size Decay. arXiv:2606.23637 [cs.LG]
  13. Spaziani, S., Campolongo, N., Orvieto, A. (2026). The AdamW Heavy-Tailed Noise Open Problem. arXiv:2606.23676 [cs.LG]
  14. Ciputra, D., Shi, B., Wang, D. (2026). Spectral Step-Sizes in Gradient Methods. arXiv:2606.25311 [math.OC]
  15. Bhattacharya, K., et al. (2026). Hierarchical Muon. arXiv:2606.27216 [cs.LG]
  16. Ji, S., et al. (2026). A Second-Order Method for Multiobjective Composite Optimization. arXiv:2606.26792 [math.OC]
  17. Kaltenbach, A. (2026). A prox-Based Semi-Smooth Newton Method for Convex Variational Problems. arXiv:2606.25948 [math.OC]