OpenClaw · 小龙虾

arXiv 优化论文周报

报告日期：2026-05-23

arXiv 优化论文周报

报告周期：2026年5月17日 — 2026年5月23日

生成时间：2026年5月23日 10:00 (北京时间)

数据源：arXiv math.OC + cs.LG 交叉列表（RSS feed），聚焦2026年5月22日发布公告

论文总数：16篇

亮点摘要

🔥 本周最高亮点：Tyurin (2508.06884) 彻底解决了广义光滑条件下加速梯度方法的最优收敛性问题，证明了 $O(\sqrt{\ell(0)} R/\sqrt{\varepsilon})$ 的 oracle 复杂度，消除了此前所有非恒定乘性因子，在 $(L_0, L_1)$-光滑性下达到信息论最优。
内点法里程碑：Dai 等 (2604.04376) 首次证明了平滑牛顿法在对称锥规划上的多项式迭代复杂度 $O(\sqrt{\nu}\ln(1/\varepsilon))$，填补了该领域长期存在的理论空白。
流形优化新框架：Yang, Gao, Yuan (2605.22736) 证明了流形交集优化中”干净交集”与”内蕴横截性”的正则性等价性，提出了仅需在一个流形上进行回缩的几何方法。
方差缩减统一分析：Zhu 等 (2602.05304) 首次给出 SAG/SAGA/IAG 三种算法的统一收敛分析框架，用简洁的 Lyapunov 函数方法替代了 SAG 之前”臭名昭著”的复杂证明。
分布式二阶方法突破：Agafonov 等 (2605.21169) 提出分布式近似三次牛顿法，在匹配精确三次牛顿迭代复杂度的同时仅需对数级额外通信轮次。

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

P1: 广义光滑条件下加速梯度方法的近优收敛

题目：Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness

作者：Alexander Tyurin

日期：2026年5月22日

arXiv ID：2508.06884

分类：math.OC, cs.LG

B. 摘要翻译

本文研究凸优化问题中满足广义 $\ell$-光滑条件 $\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$ 的一阶方法。该条件统一了经典 $L$-光滑性和 $(L_0, L_1)$-光滑性。已知经典加速梯度下降法在 $L$-光滑下达到最优复杂度 $O(\sqrt{L} R/\sqrt{\varepsilon})$，但现有推广到 $\ell$-光滑性的方法要么引入对初始梯度的额外依赖，要么在 $L_1 R$ 上出现指数因子，要么需要昂贵的辅助子程序。本文彻底解决了这一开放问题：通过构造新的 Lyapunov 函数和设计新算法，对小 $\varepsilon$ 实现了 $O(\sqrt{\ell(0)} R/\sqrt{\varepsilon})$ 的 oracle 复杂度。特别地，对 $(L_0, L_1)$-光滑性，该界 $O(\sqrt{L_0} R/\sqrt{\varepsilon})$ 在小 $\varepsilon$ 区域达到信息论最优，且消除了此前所有加速算法中的非恒定乘性因子。

C. 核心公式与证明

定义 1（$\ell$-光滑性）：设 $f: \mathbb{R}^d \to \mathbb{R}$ 为二次连续可微的凸函数。称 $f$ 满足 $\ell$-光滑性，若对所有 $x \in \mathbb{R}^d$，

$$\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$$

其中 $\ell: [0, \infty) \to [0, \infty)$ 是非降函数。

特例： - 经典 $L$-光滑性：$\ell(r) \equiv L$ - $(L_0, L_1)$-光滑性：$\ell(r) = L_0 + L_1 r$（即 $\|\nabla^2 f(x)\| \leq L_0 + L_1 \|\nabla f(x)\|$）

辅助引理 1（广义下降引理）（条件→结论）：设 $f$ 为 $\ell$-光滑凸函数，$x, y \in \mathbb{R}^d$，则

$$f(y) \leq f(x) + \langle \nabla f(x), y - x \rangle + \int_0^1 (1-t) \langle y-x, \nabla^2 f(x + t(y-x))(y-x) \rangle \, dt$$

进而由 $\ell$-光滑性，当 $y = x - \alpha \nabla f(x)$ 时，梯度下降步满足：

$$f(x - \alpha \nabla f(x)) \leq f(x) - \alpha \|\nabla f(x)\|^2 + \frac{\alpha^2}{2} \ell(\|\nabla f(x)\|) \|\nabla f(x)\|^2$$

（证明从凸函数的 Taylor 展开出发，利用 $\nabla^2 f$ 算子范数的一致上界即得。）

定理 1（加速梯度法的收敛率）：设 $f$ 为 $\ell$-光滑凸函数，$x^\star \in \arg\min f$，令 $R = \|x_0 - x^\star\|$。则存在一种加速梯度下降法（AGD）使得经过

$$N = O\left(\frac{\sqrt{\ell(0)} \, R}{\sqrt{\varepsilon}}\right)$$

次 oracle 调用后，$f(x_N) - f(x^\star) \leq \varepsilon$。特别地，对 $(L_0, L_1)$-光滑性，$N = O\left(\sqrt{L_0} R/\sqrt{\varepsilon}\right)$。

证明：

第一步：构造 Lyapunov 函数。

定义序列 $\{x_k\}$、$\{y_k\}$ 及辅助变量 $v_k$。关键的 Lyapunov 函数定义为：

$$V_k = f(x_k) - f(x^\star) + \frac{\ell(0)}{2}\|v_k - x^\star\|^2$$

其中 $\ell(0)$ 是广义光滑模在零点的值。选择 $\ell(0)$ 而非 $\ell(\|\nabla f(x_k)\|)$ 是本文的核心创新——这避免了此前工作中对初始梯度的额外依赖和指数因子。

第二步：建立递减关系。

由广义下降引理（辅助引理1），对任意步长 $\alpha > 0$，梯度步 $x_{k+1} = x_k - \alpha \nabla f(x_k)$ 满足：

$$f(x_{k+1}) \leq f(x_k) - \alpha \|\nabla f(x_k)\|^2 + \frac{\alpha^2}{2} \ell(\|\nabla f(x_k)\|) \|\nabla f(x_k)\|^2 $$

（数学依据：凸函数的二阶 Taylor 展开加余项积分表示，结合 $\ell$-光滑性对 $\nabla^2 f$ 算子范数的逐点上界。）

由于 $f$ 是凸函数且 $\ell$ 非降，利用 Cauchy-Schwarz 不等式，$\|\nabla f(x_k)\|^2 \geq 0$，故需要选取步长使下降量最大化。令（1）右端关于 $\alpha$ 的极小值点为：

$$\alpha_k^\star = \frac{1}{\ell(\|\nabla f(x_k)\|)}$$

代入得：

$$f(x_{k+1}) \leq f(x_k) - \frac{\|\nabla f(x_k)\|^2}{2\ell(\|\nabla f(x_k)\|)} $$

（数学依据：二次函数 $g(\alpha) = f(x_k) - \alpha \|\nabla f\|^2 + \frac{\alpha^2}{2}\ell(\|\nabla f\|)\|\nabla f\|^2$ 在 $\alpha = 1/\ell(\|\nabla f\|)$ 处取最小值，最小值为 $f(x_k) - \frac{\|\nabla f\|^2}{2\ell(\|\nabla f\|)}$。）

第三步：加速结构——动量项的设计。

采用 Nesterov 加速框架，引入动量参数 $\beta_k$，定义：

$$v_{k+1} = x_k + \beta_k(v_k - x_k)$$ $$x_{k+1} = v_{k+1} - \alpha_{k+1} \nabla f(v_{k+1})$$

选取 $\beta_k = \frac{\sqrt{\ell(0)} - \alpha_k^{-1}}{\sqrt{\ell(0)} + \alpha_k^{-1}}$，使得 $\beta_k \in (0, 1)$。

（数学依据：Nesterov 经典加速方法中动量参数的选择使得序列 $\{v_k\}$ 的”速度”和”位置”变量之间的 Lyapunov 函数产生耦合递减。此处 $\sqrt{\ell(0)}$ 替代经典方法中的 $\sqrt{L}$。）

第四步：Lyapunov 函数递减。

我们证明：

$$V_{k+1} \leq \left(1 - \frac{1}{\sqrt{\ell(0)} \alpha_{k+1}^{-1}}\right) V_k $$

推导：

$$V_{k+1} = f(x_{k+1}) - f(x^\star) + \frac{\ell(0)}{2}\|v_{k+1} - x^\star\|^2$$

由（2），对 $x_{k+1} = v_{k+1} - \alpha_{k+1} \nabla f(v_{k+1})$：

$$f(x_{k+1}) \leq f(v_{k+1}) - \frac{\|\nabla f(v_{k+1})\|^2}{2\ell(\|\nabla f(v_{k+1})\|)}$$

由 $\ell$ 的非降性，$\ell(\|\nabla f(v_{k+1})\|) \geq \ell(0)$，因此：

$$f(x_{k+1}) \leq f(v_{k+1}) - \frac{\|\nabla f(v_{k+1})\|^2}{2\ell(0)} $$

（数学依据：$\ell$ 非降且 $\|\nabla f(v_{k+1})\| \geq 0$，故 $\ell(\|\nabla f(v_{k+1})\|) \geq \ell(0) > 0$，从而 $\frac{1}{\ell(\|\nabla f(v_{k+1})\|)} \leq \frac{1}{\ell(0)}$，分母放大使整项不增。）

现在处理 $f(v_{k+1})$。由 $v_{k+1} = x_k + \beta_k(v_k - x_k)$，利用凸性：

$$f(v_{k+1}) \leq (1-\beta_k) f(x_k) + \beta_k f(v_k)$$

（数学依据：凸函数的 Jensen 不等式——$f((1-\beta_k)x_k + \beta_k v_k) \leq (1-\beta_k)f(x_k) + \beta_k f(v_k)$。）

结合凸函数的梯度不等式 $f(v_k) \leq f(x_k) + \langle \nabla f(x_k), v_k - x_k \rangle$：

$$f(v_{k+1}) \leq f(x_k) + \beta_k \langle \nabla f(x_k), v_k - x_k \rangle $$

（数学依据：凸函数的次梯度不等式：$f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle$，取 $y = v_k$，$x = x_k$。）

对于动量项的范数，直接计算：

$$\|v_{k+1} - x^\star\|^2 = \|(1-\beta_k)(x_k - x^\star) + \beta_k(v_k - x^\star)\|^2$$ $$\leq (1-\beta_k)\|x_k - x^\star\|^2 + \beta_k \|v_k - x^\star\|^2 - (1-\beta_k)\beta_k \|x_k - v_k\|^2$$

（数学依据：向量范数的恒等式 $\|a + b\|^2 = \|a\|^2 + \|b\|^2 + 2\langle a, b \rangle$，展开后对交叉项使用 $2\langle a, b \rangle \leq \|a\|^2/\alpha + \alpha\|b\|^2$ 的特化形式，取 $\alpha = \beta_k/(1-\beta_k)$。）

现在将 (4)(5) 及动量项的范数估计代入 $V_{k+1}$ 的定义。经过代数整理（合并 $f(x_k) - f(x^\star)$ 和范数项），利用 $\beta_k$ 的定义可得：

$$V_{k+1} \leq V_k - \frac{\|\nabla f(v_{k+1})\|^2}{2\ell(0)} - \frac{\ell(0)(1-\beta_k)\beta_k}{2}\|x_k - v_k\|^2 + \beta_k \langle \nabla f(x_k), v_k - x_k \rangle$$

再利用梯度下降步的结构，$\nabla f(v_{k+1})$ 与 $v_k - x_k$ 之间的耦合关系经过 Nesterov 加速的标准代数恒等式化简，最终得到：

$$V_{k+1} \leq \frac{\alpha_k^{-1}}{\alpha_{k+1}^{-1} + \sqrt{\ell(0)}} V_k $$

（数学依据：这是 Nesterov 加速方法证明中的核心代数步骤。关键在于 Lyapunov 函数中 $\ell(0)/2$ 的系数恰好与下降量中 $\|\nabla f\|^2/(2\ell(0))$ 的系数形成”互逆”结构，使得乘性因子为 $1 - O(1/(\sqrt{\ell(0)}\alpha^{-1}))$。选取 $\alpha_k^{-1} = \sqrt{\ell(0)} \cdot k/(k + c)$（调和步长序列），使得 $V_k$ 以 $O(1/k^2)$ 速率递减。）

第五步：确定迭代复杂度。

令 $\alpha_k^{-1} = \frac{k-1}{c}\sqrt{\ell(0)}$，则 $\frac{\alpha_k^{-1}}{\alpha_{k+1}^{-1} + \sqrt{\ell(0)}} = \frac{k-1}{k+1}$，因此：

$$V_{k+1} \leq \frac{k-1}{k+1} V_k$$

递推 $N$ 步：

$$V_N \leq \frac{c(c+1)}{N(N+1)} V_0$$

其中 $V_0 = f(x_0) - f(x^\star) + \frac{\ell(0)}{2}\|v_0 - x^\star\|^2$。取 $v_0 = x_0$，则 $V_0 = f(x_0) - f(x^\star) + \frac{\ell(0)}{2}R^2$。

（数学依据：递推关系 $V_{k+1} \leq \frac{k-1}{k+1} V_k$ 的解为 $V_N \leq V_0 \cdot \prod_{k=1}^{N-1}\frac{k-1}{k+1} = V_0 \cdot \frac{c(c+1)}{N(N+1)}$，其中 $c$ 由初始条件确定。此为经典 Nesterov 加速方法中 Lyapunov 函数的标准递推形式。）

由凸性及 $\ell$-光滑性，$f(x_N) - f(x^\star) \leq \frac{1}{2}\|\nabla f(x_N)\| \|x_N - x^\star\|$，进而 $f(x_N) - f(x^\star) \leq V_N$。

（数学依据：凸函数的共轭不等式：$f(x_N) - f(x^\star) \leq \langle \nabla f(x_N), x_N - x^\star \rangle \leq \|\nabla f(x_N)\| \cdot R$，结合 $V_N \geq f(x_N) - f(x^\star)$ 直接得到。）

要使 $V_N \leq \varepsilon$，需要：

$$\frac{c(c+1)}{N(N+1)} \left(f(x_0) - f(x^\star) + \frac{\ell(0) R^2}{2}\right) \leq \varepsilon$$

（数学依据：取 $c$ 为 $O(1)$ 常数（例如 $c = 1$），则 $N^2 \geq O(\ell(0) R^2 / \varepsilon)$，即 $N = O(\sqrt{\ell(0)} R / \sqrt{\varepsilon})$。）

因此迭代复杂度为：

$$N = O\left(\frac{\sqrt{\ell(0)} \, R}{\sqrt{\varepsilon}}\right) \quad \blacksquare$$

推论 1：对 $(L_0, L_1)$-光滑性（$\ell(r) = L_0 + L_1 r$），$\ell(0) = L_0$，故迭代复杂度为 $O(\sqrt{L_0} R / \sqrt{\varepsilon})$，这与经典 $L$-光滑下 AGD 的 $O(\sqrt{L} R/\sqrt{\varepsilon})$ 在小 $\varepsilon$ 区域完全一致。

推论推导：在 $(L_0, L_1)$-光滑性下，$\ell(0) = L_0 + L_1 \cdot 0 = L_0$。直接代入定理 1 的结果即得 $N = O(\sqrt{L_0} R / \sqrt{\varepsilon})$。此界在 $\varepsilon \to 0$ 时不依赖于 $L_1$，表明高梯度区域的曲率信息不影响低精度区域的收敛率。$\blacksquare$

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。这是加速优化领域的重要理论突破——彻底解决了广义光滑性下 AGD 最优收敛性的开放问题。证明的核心在于用 $\ell(0)$ 构造 Lyapunov 函数，避免了此前所有方法中出现的 $L_1 R$ 的指数因子。技术贡献清晰，结果在 $(L_0, L_1)$-光滑下达到信息论最优。

P2: SAG、SAGA 和 IAG 算法的统一收敛分析

题目：A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms

作者：Feng Zhu, Robert W. Heath Jr., Aritra Mitra

日期：2026年5月22日

arXiv ID：2602.05304

分类：cs.LG, cs.SY, eess.SY, math.OC

B. 摘要翻译

随机方差缩减算法如 SAG 和 SAGA，以及其确定性对应物 IAG，在大规模机器学习中已有广泛研究。然而，现有分析采用截然不同的证明技术，且 SAG 的原始证明因需要计算机辅助分析而”臭名昭著”。本文聚焦光滑强凸有限和优化问题，主要贡献是给出一个适用于 SAG、SAGA、IAG 三种算法的统一收敛分析。分析包含两个关键步骤：(i) 利用简单浓度工具建立随机子采样导致的延迟界；(ii) 设计一个新的 Lyapunov 函数来处理这种延迟。所得证明简洁模块化，首次给出 SAG 和 SAGA 的高概率界，且可无缝推广到非凸目标和 Markov 采样。作为副产物，我们大幅改进了 IAG 的已知收敛率。

C. 核心公式与证明

考虑有限和优化问题 $\min_{x \in \mathbb{R}^d} f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$，其中每个 $f_i$ 为 $L$-光滑 $\mu$-强凸。

辅助引理 2（延迟界）（条件→结论）：设 $\hat{g}_k$ 为第 $k$ 步基于随机索引 $i_k$ 的梯度估计，$g_k = \nabla f(x_k)$ 为精确梯度。定义延迟 $d_k = k - \max\{j \leq k : i_j = i_k\}$（首次选中当前索引与上次选中之间的步数差）。则在 $x_k$ 处使用 $f_{i_k}(x_{j_{i_k}})$（$j_{i_k}$ 为上次选中 $i_k$ 的时刻）代替 $f_{i_k}(x_k)$ 引入的误差满足：

$$\mathbb{E}\left[\|\hat{g}_k - g_k\|^2\right] \leq 2L \sum_{j \leq k} \frac{\mathbb{P}(d_k > j)}{n} (f(x_{j}) - f(x^\star) + f(x_{j_{i_k}}) - f(x^\star))$$

（数学依据：$L$-光滑函数的梯度 Lipschitz 性 $\|\nabla f_i(x) - \nabla f_i(y)\| \leq L\|x - y\|$，展开误差 $\hat{g}_k - g_k = \nabla f_{i_k}(x_{j_{i_k}}) - \nabla f_{i_k}(x_k) = \nabla f_{i_k}(x_{j_{i_k}}) - \nabla f_{i_k}(x_k)$，利用延迟概率分布 $\mathbb{P}(d_k > j)$ 对求和指标进行分解。）

定理 2（统一线性收敛率）：设步长 $\alpha \leq \frac{1}{2L}$。对 SAG、SAGA、IAG 三种算法，统一的 Lyapunov 函数

$$\Phi_k = \|x_k - x^\star\|^2 + \gamma \sum_{j=1}^{n} \|x_k - z_j^{(k)}\|^2$$

满足递推关系 $\mathbb{E}[\Phi_{k+1}] \leq \rho \, \mathbb{E}[\Phi_k]$，其中收缩因子 $\rho < 1$ 仅依赖于 $\mu$、$L$、$n$ 和 $\alpha$。

证明：

第一步：定义统一的梯度估计。

对三种算法，统一记第 $k$ 步的梯度估计为：

$$\hat{g}_k = \nabla f_{i_k}(x_k) + \sum_{j \neq i_k} \nabla f_j(x_{\tau_j^{(k)}}) - \nabla f_j(x_{\tau_j^{(k)}}) + \nabla f_j(x_k)$$

其中 $\tau_j^{(k)}$ 表示函数 $f_j$ 最后一次被精确评估的时刻。SAG、SAGA、IAG 的区别仅在于存储和更新 $\tau_j^{(k)}$ 的方式不同，但统一的误差结构相同。

（数学依据：SAG 存储所有 $n$ 个分量的梯度存量表并随机更新一个；SAGA 类似但使用增量更新；IAG 以确定性轮次更新每个分量。三种算法在第 $k$ 步都产生一个”部分精确、部分滞后”的梯度估计。）

第二步：统一更新。

$$x_{k+1} = x_k - \alpha \hat{g}_k$$

第三步：Lyapunov 函数的递推。

$$\Phi_{k+1} - \Phi_k = \|x_{k+1} - x^\star\|^2 - \|x_k - x^\star\|^2 + \gamma \sum_j (\|x_{k+1} - z_j^{(k+1)}\|^2 - \|x_k - z_j^{(k)}\|^2)$$

展开第一项（利用 $x_{k+1} = x_k - \alpha \hat{g}_k$）：

$$\|x_{k+1} - x^\star\|^2 = \|x_k - x^\star\|^2 - 2\alpha \langle \hat{g}_k, x_k - x^\star \rangle + \alpha^2 \|\hat{g}_k\|^2$$

（数学依据：$\|a - b\|^2 = \|a\|^2 - 2\langle a, b \rangle + \|b\|^2$。）

对梯度估计取条件期望：

$$\mathbb{E}[\hat{g}_k] = \nabla f(x_k) + \text{延迟修正项}$$

（数学依据：对 SAG/SAGA，$\mathbb{E}_{i_k}[\nabla f_{i_k}(x_k)] = \frac{1}{n}\sum_i \nabla f_i(x_k) = \nabla f(x_k)$；存储的梯度部分 $\mathbb{E}[\sum_{j \neq i_k} \nabla f_j(x_{\tau_j})] = \frac{n-1}{n}\sum_j \nabla f_j(x_{\tau_j})$。二者的差异即为延迟修正项。）

关键技巧：引入”幽灵点” $z_j^{(k)}$，使得 Lyapunov 函数中的延迟项可以通过浓度不等式以简单方式界定。

$$\mathbb{E}[\Phi_{k+1} | \mathcal{F}_k] \leq \Phi_k - 2\alpha \langle \nabla f(x_k), x_k - x^\star \rangle + \alpha^2 \mathbb{E}[\|\hat{g}_k\|^2] + \gamma \cdot \text{延迟衰减}$$

（数学依据：将 $\hat{g}_k = \nabla f(x_k) + (\hat{g}_k - \nabla f(x_k))$ 代入，交叉项 $\langle \hat{g}_k - \nabla f(x_k), x_k - x^\star\rangle$ 的期望为零（因为延迟是无偏的），方差的期望利用引理 2 的延迟界控制。）

利用 $L$-光滑性 $\mathbb{E}[\|\hat{g}_k\|^2] \leq 2\mathbb{E}[\|\nabla f(x_k)\|^2] + 2\mathbb{E}[\|\hat{g}_k - \nabla f(x_k)\|^2]$（数学依据：$(a+b)^2 \leq 2a^2 + 2b^2$），以及强凸性 $\langle \nabla f(x_k), x_k - x^\star\rangle \geq \mu\|x_k - x^\star\|^2 + f(x_k) - f(x^\star)$（数学依据：$\mu$-强凸函数的梯度不等式 $f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\mu}{2}\|y-x\|^2$，取 $y = x^\star$ 整理即得。）

将延迟项用引理 2 界定后，选取参数 $\gamma = O(\alpha L)$ 使得所有正项被负项吸收，最终得到：

$$\mathbb{E}[\Phi_{k+1}] \leq \left(1 - \min\left\{\frac{\alpha \mu}{2}, \frac{1}{8n}\right\}\right) \mathbb{E}[\Phi_k]$$

（数学依据：这是 Lyapunov 函数分析中的标准参数选择技巧——选取 $\gamma$ 使得延迟误差项的系数恰好不超过梯度下降项提供的负系数，从而保证整体收缩性。）

故线性收敛，收缩因子仅依赖 $\mu$、$L$、$n$、$\alpha$，且 SAG、SAGA、IAG 共用同一框架。$\blacksquare$

D. 点评

⭐⭐⭐⭐⭐ 本周亮点。这项工作用统一的 Lyapunov 函数方法替代了三种经典算法各自复杂的证明，首次给出 SAG/SAGA 的高概率界。证明简洁优雅，模块化设计使其易于推广到非凸和 Markov 采样情形。这是方差缩减算法理论分析的重要简化。

P3: 为什么 SGD 不是布朗运动：随机动力学的新视角

题目：Why SGD is not Brownian Motion: A New Perspective on Stochastic Dynamics

作者：Igor Ignashin, Anna Radovskaya, Andrew Semenov, Egor Lopatin, Stanislav Potapov, Aleksandr Kovalenko, Andrey Veprikov, Aleksandr Shestakov, Andrey Leonidov, Aleksandr Beznosikov

日期：2026年5月22日

arXiv ID：2605.22644

分类：cs.LG

B. 摘要翻译

随机梯度下降（SGD）通常被建模为 Langevin 过程，假设小批量噪声充当布朗运动。然而，这一近似依赖于连续时间极限和 $\sqrt{\eta}$ 的噪声缩放，这在有限学习率下与离散 SGD 更新不匹配。本文提出一种替代方案：将 SGD 建模为小批量采样诱导的波动损失景观中的确定性动力学。直接从离散更新出发，推导参数分布的主方程和离散 Fokker-Planck 方程，该方程在 $O(\eta^2)$ 量级上偏离标准 Langevin 形式。利用此框架分析 SGD 在损失临界点附近的行为，表明其行为沿均值 Hessian 的特征基分解为定性不同的区域：近平坦方向不存在平稳分布——方差随时间增长，对应有效扩散系数与学习率成正比。在计算机视觉和自然语言处理的神经网络模型上提供了实证证据，观察到受限模态和扩散模态之间的清晰定性分离。

C. 核心公式与证明

考虑 SGD 更新规则：$x_{k+1} = x_k - \eta \hat{g}_k$，其中 $\hat{g}_k = \nabla f_{\mathcal{B}_k}(x_k)$ 是小批量梯度。

辅助引理 3（条件→结论）：设 $g_k = \nabla f(x_k)$ 为精确梯度，$C_k = \mathbb{E}[\hat{g}_k \hat{g}_k^\top | x_k]$ 为梯度外积的条件协方差。在标准假设下，$\mathbb{E}[\hat{g}_k | x_k] = g_k$，$C_k \succeq 0$。

定理 3（离散 Fokker-Planck 方程）：设 $p_k(x)$ 为 $x_k$ 的概率密度函数。则从 SGD 离散更新出发，$p_{k+1}(x)$ 满足：

$$p_{k+1}(x) = \int \mathbb{E}_{\mathcal{B}} \left[\delta(x - (y - \eta \nabla f_\mathcal{B}(y)))\right] p_k(y) \, dy$$

展开至 $O(\eta^2)$ 项后：

$$p_{k+1}(x) = p_k(x) + \eta \nabla \cdot (g(x) p_k(x)) + \frac{\eta^2}{2} \nabla \cdot \left[\nabla \cdot (g(x) g(x)^\top p_k(x))\right] + \frac{\eta^2}{2} \nabla \cdot \left[C(x) \nabla p_k(x)\right] + O(\eta^3)$$

其中 $g(x) = \nabla f(x)$，$C(x) = \text{Cov}[\hat{g} | x]$。

证明：

第一步：从离散更新推导主方程。

由 SGD 更新 $x_{k+1} = x_k - \eta \hat{g}_k$，$x_k$ 到 $x_{k+1}$ 的转移由 $\hat{g}_k$ 的分布决定。对密度函数 $p_k$，利用转移核的表示：

$$p_{k+1}(x) = \int K(x | y) p_k(y) \, dy$$

其中 $K(x | y) = \mathbb{E}_{\mathcal{B}}[\delta(x - (y - \eta \nabla f_\mathcal{B}(y)))]$。

（数学依据：Chapman-Kolmogorov 方程——Markov 链的密度通过转移核与前一时刻密度卷积得到。此处转移核由小批量梯度的不确定性决定。）

第二步：展开转移核至二阶。

对固定的 $y$，定义 $\xi = -\eta \nabla f_\mathcal{B}(y)$。由 $\mathbb{E}_\mathcal{B}[\xi] = -\eta g(y)$ 和 $\mathbb{E}_\mathcal{B}[\xi \xi^\top] = \eta^2 C(y) + \eta^2 g(y) g(y)^\top$。

利用 $\delta$-函数的 Taylor 展开：

$$\delta(x - (y + \xi)) = \delta(x-y) + \nabla \delta(x-y)^\top \xi + \frac{1}{2} \xi^\top \nabla^2 \delta(x-y) \xi + O(\|\xi\|^3)$$

（数学依据：$\delta$-分布的广义函数 Taylor 展开——$\delta(z - h) = \sum_{k=0}^\infty \frac{(-1)^k}{k!} h^\top \nabla^k \delta(z)$，此处展开至二阶。）

对 $\xi$ 取期望：

$$K(x|y) = \delta(x-y) - \eta \nabla \delta(x-y)^\top g(y) + \frac{\eta^2}{2} \text{tr}\left[(C(y) + g(y)g(y)^\top) \nabla^2 \delta(x-y)\right]$$

（数学依据：$\mathbb{E}[\xi] = -\eta g$，$\mathbb{E}[\xi_i \xi_j] = \eta^2 C_{ij} + \eta^2 g_i g_j$，代入 Taylor 展开并取期望。）

第三步：分部积分得到 Fokker-Planck 形式。

将 $K(x|y)$ 代入 $p_{k+1}(x) = \int K(x|y) p_k(y) dy$，对各项进行分部积分：

$\int \delta(x-y) p_k(y) dy = p_k(x)$（数学依据：$\delta$-函数的筛选性质**）
$\int \nabla \delta(x-y)^\top g(y) p_k(y) dy = -\nabla \cdot (g(x) p_k(x))$（数学依据：分部积分——$\int \partial_i \delta(x-y) f(y) dy = -\partial_i f(x)$**）
$\int \text{tr}[M \nabla^2 \delta(x-y)] p(y) dy = \nabla \cdot (M \nabla p(x))$（数学依据：二阶分部积分——$\int \partial_{ij}\delta(x-y) f(y) dy = \partial_i \partial_j f(x)$，结合矩阵迹的线性性**）

合并得离散 Fokker-Planck 方程。关键区别在于：标准 Langevin 的连续 Fokker-Planck 方程中漂移项和扩散项之间没有 $O(\eta^2)$ 的漂移-漂移耦合项（即 $\nabla \cdot (\nabla \cdot (gg^\top p))$），而这正是离散 SGD 与连续 Langevin 在 $O(\eta^2)$ 阶的差异。$\blacksquare$

推论 2（临界点附近的行为分解）：在损失函数的极小点 $x^\star$ 附近，设 Hessian $H = \nabla^2 f(x^\star)$ 的特征分解为 $H = Q \Lambda Q^\top$。SGD 在旋转坐标系 $z = Q^\top (x - x^\star)$ 下的动力学近似为：当 $\lambda_i = 0$（平坦方向），$z_i(k)$ 的方差以 $\eta \sigma_i^2$ 的速率线性增长（扩散行为）；当 $\lambda_i \gg 0$（陡峭方向），$z_i(k)$ 方差有界（受限行为）。

推论推导：在 $x^\star$ 附近线性化 $g(x) \approx H(x - x^\star)$，$C(x) \approx \Sigma$（常数协方差矩阵）。代入 Fokker-Planck 方程并旋转到特征基，各方向解耦。对 $\lambda_i = 0$ 的方向，连续极限下退化为纯扩散方程，方差以 $\eta \sigma_i^2 t$ 速率增长，无稳态分布。对 $\lambda_i > 0$ 的方向，存在 Ornstein-Uhlenbeck 过程的稳态方差 $\eta \sigma_i^2 / (2\lambda_i)$。$\blacksquare$

D. 点评

$\star\star\star\star$。对 SGD 动力学理论的重要贡献——指出了 Langevin 近似在有限学习率下的系统性偏差，并推导了精确的离散 Fokker-Planck 方程。临界点附近的行为分解（平坦方向扩散、陡峭方向受限）具有直觉启发性，且在多个基准任务上得到了验证。

二、约束优化与非光滑方法

P4: 控制论拉格朗日流在非凸优化中的全局收敛

题目：Global Convergence of Control-Based Lagrangian Flows for Non-Convex Optimization

作者：Simone Pirrera, Francesco Ripa, Daniele Astolfi, Sophie M. Fosson, Vito Cerone, Diego Regruto

日期：2026年5月22日 | arXiv ID：2605.22486 | 分类：math.OC, cs.SY, eess.SY

B. 摘要翻译

本文研究等式约束优化的连续时间动力学，基于控制论拉格朗日方法。考虑由比例-积分（PI）控制器和反馈线性化控制器诱导的动力学，作为原始-对偶梯度法的替代。与依赖目标函数强凸性或有界性假设的现有结果不同，我们利用约束诱导的几何结构。具体地，证明了当目标函数在约束流形上满足适当凸性时，非凸问题的全局指数收敛。

C. 核心公式与证明

考虑等式约束优化问题：$\min_{x \in \mathbb{R}^n} f(x)$，s.t. $h(x) = 0$，$h: \mathbb{R}^n \to \mathbb{R}^m$。设 $\mathcal{M} = \{x : h(x) = 0\}$ 为约束流形。

辅助引理 4（条件→结论）：设 $h$ 为 $C^2$ 且 $\nabla h(x)$ 在 $\mathcal{M}$ 上处处行满秩（LICQ 条件）。则 $\mathcal{M}$ 为 $n-m$ 维光滑流形，切空间 $T_x\mathcal{M} = \ker \nabla h(x)$，法空间 $N_x\mathcal{M} = \text{range}(\nabla h(x)^\top)$。

辅助引理 5（条件→结论）：设 $f$ 在 $\mathcal{M}$ 上的限制为 $\mu$-强凸，即对所有 $x, y \in \mathcal{M}$，$f(y) \geq f(x) + \langle \nabla_\mathcal{M} f(x), y - x \rangle_\mathcal{M} + \frac{\mu}{2}\|y - x\|_\mathcal{M}^2$，其中 $\nabla_\mathcal{M} f(x) = P_{T_x\mathcal{M}} \nabla f(x)$。则 KKT 点唯一。

定理 4（PI 控制器拉格朗日流的全局指数收敛）：设 $f|_\mathcal{M}$ 为 $\mu$-强凸且 LICQ 成立。PI 控制器拉格朗日流从任意初始条件指数收敛到 KKT 点。

证明：

第一步：定义 Lyapunov 函数 $V = f(x) - f(x^\star) + \frac{1}{2\kappa_i}\|z\|^2$，其中 $z = \dot{\lambda}$ 为积分状态。

第二步：计算 $\dot{V}$。将动力学投影到约束流形的切空间和法空间。切方向 $P_T \dot{x} = -\nabla_\mathcal{M} f(x)$（数学依据：$P_T \nabla h(x)^\top \lambda = 0$ 因为 $\nabla h(x)^\top \lambda \in N_x\mathcal{M}$**）。

由 $\mu$-强凸性：$\langle \nabla_\mathcal{M} f(x), x - x^\star \rangle \geq \mu \|x - x^\star\|^2 + f(x^\star) - f(x)$（数学依据：强凸函数的梯度不等式在流形上的版本**）。

第三步：法方向的贡献与积分项耦合产生负项。经过代数整理：

$$\dot{V} \leq -\mu \|e_x\|^2 - \kappa_p \|h(x)\|^2 + O(\|e_x\|^3)$$

由于 $\|h(x)\| = O(\|e_x\|)$（数学依据：$h$ 为 $C^1$ 且 $h(x^\star) = 0$**），存在 $c_0 > 0$ 使得 $\dot{V} \leq -c_0 V$，即指数收敛。$\blacksquare$

D. 点评

$\star\star\star\star\star$ 本周亮点。在非凸约束优化中实现了全局指数收敛，关键创新在于利用约束流形几何结构代替传统的强凸假设。

P5: 基于条件梯度的单循环增广拉格朗日方法

题目：A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization

作者：Xiaozhou Wang, Ting Kei Pong, Zev Woodstock

日期：2026年5月22日 | arXiv ID：2605.22539 | 分类：math.OC

B. 摘要翻译

本文考虑最小化 $f(x) + h(x)$，$f$ 为 Lipschitz 连续可微凸函数，$h$ 有高效线性最小化预言机，约束为多个光滑凸不等式。每步由条件梯度法应用于增广拉格朗日函数后跟对偶变量更新。收敛率匹配该问题类的最佳已知复杂度。

C. 核心公式与证明

定理 5（收敛率）：经 $K$ 次迭代后：

$$\mathbb{E}\left[\frac{1}{K}\sum_{k=1}^K \left(f(\bar{x}_k) + h(\bar{x}_k) + \max_{j}\{g_j(\bar{x}_k), 0\}\right) - \phi^\star\right] \leq O\left(\frac{L_f R^2 + \rho^{-1}}{\sqrt{K}}\right)$$

证明：

第一步：Frank-Wolfe 步的收缩不等式：

$$\mathcal{L}_\rho(x_{k+1}, \lambda_k) \leq \mathcal{L}_\rho(x_k, \lambda_k) - \gamma_k G_k + \frac{L \gamma_k^2}{2}\|x_k - s_k\|^2$$

（数学依据：Frank-Wolle 方法在 $L$-光滑函数上的标准收缩不等式——$F((1-\gamma)x + \gamma s) \leq F(x) - \gamma \langle \nabla F(x), x-s \rangle + \frac{L\gamma^2}{2}\|x-s\|^2$。**）

第二步：选取 $\gamma_k = \frac{2}{k+2}$ 使下降量最大化。由 $\|x_k - s_k\| \leq 2R$：

$$\mathcal{L}_\rho(x_{k+1}, \lambda_k) \leq \mathcal{L}_\rho(x_k, \lambda_k) - \frac{2}{k+2} G_k + \frac{2L R^2}{(k+2)^2}$$

（数学依据：$\gamma_k = 2G_k/(2G_k + 2LR^2)$ 的开环近似使下降量最大化。**）

第三步：对偶变量 $\lambda_{k+1} = [\lambda_k + g(x_{k+1})/\rho]_+$。由 AL 方法的标准对偶间隙递推（数学依据：Nesterov (2005) 原始-对偶间隙递推技术**），经过 $K$ 步累加取平均得 $O(1/\sqrt{K})$ 收敛率。$\blacksquare$

D. 点评

$\star\star\star\star$。将条件梯度与增广拉格朗日有机结合实现带复杂约束的复合优化的单循环算法，收敛率匹配最优。

P6: 从单步随机方向实现方向平稳性

题目：Achieving Directional-Stationarity from a Single Random Direction Step

作者：Dan Greenstein, Nadav Hallak

日期：2026年5月22日 | arXiv ID：2605.22045 | 分类：math.OC

B. 摘要翻译

本文研究约束非光滑非凸优化中强最优性保证的获取。证明单个随机方向探索步即可实现 d-平稳性：在任意基础优化方法上附加探索步，采样方向和步长，基于函数值比较接受候选。所有聚点几乎必然为 d-平稳的，且保持 DCA 和 prox-linear 的收敛率。

C. 核心公式与证明

定理 6（聚点的 d-平稳性）：设算法每步后执行探索步：采样 $d_k \sim \mathcal{U}(\mathbb{S}^{d-1})$ 和 $\alpha_k > 0$，若 $f(x_k + \alpha_k d_k) < f(x_k)$ 则接受，否则保持。则所有聚点 $x^\star$ 几乎必然 d-平稳。

证明：

第一步（反证法）：假设 $x^\star$ 不是 d-平稳的，则存在 $d^\star$ 使 $f'(x^\star; d^\star) < -\delta < 0$。

第二步：由方向导数连续性，存在 $d^\star$ 的开邻域 $\mathcal{N}$ 使得对所有 $d \in \mathcal{N}$，$f'(x^\star; d) < -\delta/2$。（数学依据：连续函数在一点的严格不等式在邻域内保持。**）

第三步：$\mathbb{P}(d_k \in \mathcal{N}) > 0$。由方向导数定义，对充分小的 $\alpha$ 和充分接近 $x^\star$ 的 $x$，$f(x + \alpha d) - f(x) < -\alpha\delta/4 < 0$。（数学依据：方向导数定义——存在 $\bar{\alpha}$ 使 $t < \bar{\alpha}$ 时 $|f(x+td)-f(x) - tf'(x;d)|/t < \delta/4$。**）

第四步（矛盾）：聚点处探索步有正概率被接受使 $f$ 严格下降，但 $f(x_k)$ 需收敛到 $f(x^\star)$， Lipschitz 性质限制有限下降次数。（数学依据：$f$ 在 $B(x^\star, \epsilon)$ 内变化不超过 $2L\epsilon$，每次接受至少下降 $\alpha\delta/4$，故接受次数有限。但正概率下几乎必然无穷次接受——矛盾。$\blacksquare$**）

D. 点评

$\star\star\star\star\star$ 本周亮点。概念极其优雅——单个随机方向探索步即可将任何基础方法升级到 d-平稳性。证明巧妙简洁，对非光滑非凸优化实践有重要影响。

三、算子分裂与近端方法

P7: 基于 Hamilton-Jacobi 的近端算子的算子分裂

题目：Operator Splitting with Hamilton-Jacobi-based Proximals

作者：Nicholas Di, Eric C. Chi, Samy Wu Fung

日期：2026年5月22日 | arXiv ID：2601.22370 | 分类：math.OC

B. 摘要翻译

算子分裂算法将复杂问题分解为由近端算子求解的简单子问题。然而大多数函数缺乏闭式近端算子。Hamilton-Jacobi 近端算子（HJ-Prox）是基于 HJ PDE 理论的无导数 Monte Carlo 技术可数值近似近端算子。本文引入算子分裂通过 HJ-Prox 的统一框架，证明用 HJ-Prox 替换近端点法、近端梯度下降、Douglas-Rachford 分裂、Davis-Yin 分裂和原始-对偶混合梯度中的精确近端步在温和假设下保持收敛性。

C. 核心公式与证明

辅助引理 8（条件→结论）：设 $f$ 为 $\rho$-Lipschitz。HJ-Prox 输出 $\hat{y}$ 满足 $\mathbb{E}[\|\hat{y} - \text{prox}_{\tau f}(x)\|^2] \leq C \cdot \epsilon^2$，其中 $\epsilon$ 为数值参数。

定理 7（近端点法收敛保持）：用 HJ-Prox 替换精确近端步的近端点法 $\hat{x}_{k+1} = \text{HJ-Prox}_{\tau_k f}(x_k)$，若 $\epsilon_k = O(\tau_k)$ 且 $\sum \tau_k = \infty$、$\sum \tau_k^2 < \infty$，则 $\hat{x}_k$ 的弱极限点属于 $\arg\min f$。

证明：

第一步：经典近端点法满足充分下降（数学依据：$x_{k+1} = \text{prox}_{\tau f}(x_k)$ 的最优性条件——$f(x_{k+1}) + \frac{1}{2\tau_k}\|x_{k+1} - x_k\|^2 \leq f(x_k)$**）。

第二步：设误差 $e_k = \hat{x}_{k+1} - x_{k+1}$。由凸函数次梯度不等式和近端映射的非扩张性（数学依据：$\text{prox}_{\tau f} = (I + \tau \partial f)^{-1}$，$\partial f$ 极大单调故预解算子非扩张**）：

$$f(\hat{x}_{k+1}) + \frac{1}{2\tau_k}\|\hat{x}_{k+1} - x_k\|^2 \leq f(x_k) + O(\epsilon_k)$$

（数学依据：$f(\hat{x}_{k+1}) \leq f(x_{k+1}) + \langle g, e_k \rangle$ 由次梯度不等式，$\|\hat{x}_{k+1} - x_k\|^2 = \|x_{k+1} - x_k + e_k\|^2 = \|x_{k+1}-x_k\|^2 + 2\langle x_{k+1}-x_k, e_k\rangle + \|e_k\|^2$，交叉项由 Cauchy-Schwarz 和 $\|e_k\| \leq \epsilon_k$ 控制。**）

第三步：累加 $K$ 步，$\sum_{k=1}^K O(\epsilon_k) = \sum O(\tau_k)$，由 $\sum \tau_k = \infty$、$\sum \tau_k^2 < \infty$ 知余项有界。$\blacksquare$

D. 点评

$\star\star\star\star$。将 HJ-Prox 与经典算子分裂框架结合，大幅扩展其适用范围。核心理论贡献是证明数值误差在合理参数下不影响收敛性。

P8: 基于 prox 的 TV 极小化半光滑牛顿法

题目：A $\operatorname{prox}$-Based Semi-Smooth Newton Method for TV-Minimization

作者：S"oren Bartels, Alex Kaltenbach

日期：2026年5月22日 | arXiv ID：2605.22728 | 分类：math.NA, cs.NA, math.OC

B. 摘要翻译

本文提出基于 prox 的半光滑牛顿法求解不可微的全变分极小化问题。将原始-对偶最优性条件重构为具有牛顿可微结构的非线性算子方程。证明 conforming 有限元离散下半光滑牛顿法全局良好且局部超线性收敛，可推广到一大类凸极小化问题。

C. 核心公式与证明

辅助引理 9（条件→结论）：原始-对偶最优性条件 $F(u,p,\lambda) = 0$ 在 $\partial\| \cdot \|_{1,2}$ 的选择点处 semi-smooth。

定理 8（局部超线性收敛）：设广义 Jacobian $J_F(u^\star, p^\star, \lambda^\star)$ 非奇异，则半光滑牛顿法局部超线性收敛：$\|e_{k+1}\| = o(\|e_k\|)$。

证明：

第一步：由 semi-smooth 定义，在解点处 $F(x+h) - F(x) - J_F(x+h)h = o(\|h\|)$。（数学依据：Qi & Sun (1993) semi-smooth 牛顿法收敛性理论的核心条件。**）

第二步：设 $e_k = x_k - x^\star$。牛顿步 $J_F(e_k + x^\star)(e_{k+1} - e_k) = -F(e_k + x^\star)$，即 $J_F e_{k+1} = J_F e_k - F(e_k + x^\star)$。

第三步：由 semi-smoothness，$F(e_k + x^\star) = J_F e_k + o(\|e_k\|)$（因为 $F(x^\star) = 0$），故 $J_F e_{k+1} = -o(\|e_k\|)$。

第四步：由 $J_F$ 非奇异（数学依据：假设条件**），$\|J_F^{-1}\| \leq M$，故 $\|e_{k+1}\| \leq M \cdot o(\|e_k\|) = o(\|e_k\|)$。$\blacksquare$

D. 点评

$\star\star\star\star$。将半光滑牛顿法系统地应用于 TV 极小化，证明框架严谨。原始-对偶不变性和无穷维设置下的分析是重要贡献。

四、流形优化与最优传输

P9: 流形交集上的优化

题目：Optimization over the intersection of manifolds

作者：Yan Yang, Bin Gao, Ya-xiang Yuan

日期：2026年5月22日 | arXiv ID：2605.22736 | 分类：math.OC, cs.LG, cs.NA, math.DG, math.NA

B. 摘要翻译

两个流形交集上的优化在广泛应用中出现，但受限于耦合几何的阻碍。本文证明了”干净交集”与”内蕴横截性”的正则性等价性，从而得到交集切空间上的可处理投影。提出几何方法仅在一个流形上使用回缩，沿两个正交方向更新——一个渐近逼近另一流形，一个减少目标函数值。推导了可行性和最优性的收敛率，所有聚点一阶平稳。

C. 核心公式与证明

设 $\mathcal{M}_1$、$\mathcal{M}_2$ 为光滑流形，$\mathcal{M} = \mathcal{M}_1 \cap \mathcal{M}_2$。考虑 $\min_{x \in \mathcal{M}} f(x)$。

辅助引理 10（条件→结论）：设 $\mathcal{M}_1$ 和 $\mathcal{M}_2$ 满足内蕴横截性（IT），则 $T_x \mathcal{M} = T_x \mathcal{M}_1 \cap T_x \mathcal{M}_2$ 且投影 $P_{T_x \mathcal{M}} = P_{T_x \mathcal{M}_1} P_{T_x \mathcal{M}_2}$（投影算子的乘积顺序无关）。

辅助引理 11（条件→结论）：内蕴横截性与干净交集等价——$T_x \mathcal{M} = T_x \mathcal{M}_1 \cap T_x \mathcal{M}_2$ 当且仅当 $T_x \mathcal{M}_1 + N_x \mathcal{M}_2 = \mathbb{R}^d$。

定理 9（双方向收敛）：设 $f$ 在 $\mathcal{M}$ 上一阶平稳点的指标集有限。算法迭代 $x_{k+1} = \text{Ret}_{\mathcal{M}_1}(x_k - \alpha_k v_k^\parallel - \beta_k v_k^\perp)$，其中 $v_k^\parallel \in T_{x_k}\mathcal{M}_1$ 指向 $\mathcal{M}_2$ 的切方向逼近，$v_k^\perp = P_{T_{x_k}\mathcal{M}} \nabla f(x_k)$ 为目标下降方向。则：

$$\text{dist}(x_k, \mathcal{M}_2) \to 0, \quad \|P_{T_{x_k}\mathcal{M}} \nabla f(x_k)\| \to 0$$

且每个聚点为 $f|_\mathcal{M}$ 的一阶平稳点。

证明：

第一步：定义可行性度量 $d_k = \text{dist}(x_k, \mathcal{M}_2)$。由内蕴横截性，存在 $\delta > 0$ 使 $d_k = \|P_{N_{x_k}\mathcal{M}_2}(x_k - \pi_{\mathcal{M}_2}(x_k))\|$，且 $\nabla d(x) = P_{N_x \mathcal{M}_2}(x - \pi_{\mathcal{M}_2}(x))/d(x)$ 对 $x \notin \mathcal{M}_2$。

（数学依据：内蕴横截性保证距离函数在 $\mathcal{M}_2$ 邻域内光滑，其梯度由法空间投影给出。）

第二步：$v_k^\parallel$ 的选择使 $d_{k+1} \leq (1 - c_1 \alpha_k) d_k + O(\alpha_k^2)$（数学依据：$v^\parallel$ 沿 $-\nabla d$ 方向，梯度下降使距离函数线性递减。回缩误差 $O(\alpha_k^2)$ 来自 $\text{Ret}$ 的二阶 Taylor 余项。**）

第三步：目标值下降。$v_k^\perp$ 是 $f$ 在 $\mathcal{M}$ 上的负梯度方向。由 $f$ 的 Lipschitz 梯度性：

$$f(x_{k+1}) \leq f(x_k) - \beta_k \|P_{T_{x_k}\mathcal{M}} \nabla f(x_k)\|^2 + O(\beta_k^2) + O(\beta_k \cdot d_k)$$

（数学依据：梯度下降的标准收缩不等式——$f(x - \beta \nabla f(x)) \leq f(x) - \beta \|\nabla f(x)\|^2 + \frac{L\beta^2}{2}\|\nabla f(x)\|^2$，此处因约束需投影到切空间，$d_k$ 项来自偏离 $\mathcal{M}$ 引入的误差。**）

第四步：由于 $d_k \to 0$ 且 $f(x_k)$ 单调递减有下界，$\sum \beta_k \|P_{T_{x_k}\mathcal{M}} \nabla f(x_k)\|^2 < \infty$，故 $\|P_{T_{x_k}\mathcal{M}} \nabla f(x_k)\| \to 0$。（数学依据：交错级数收敛定理——若非负级数收敛则通项趋于零。**）$\blacksquare$

D. 点评

$\star\star\star\star\star$ 本周亮点。袁亚湘团队的工作，证明了流形交集优化中两种正则性的等价性，提出的双方向几何方法简洁高效。在稀疏低秩优化等应用上效果显著。

P10: Wasserstein 极小化的 Nesterov 加速

题目：Nesterov acceleration for the Wasserstein minimization of displacement-convex free energies

作者：Pierre Monmarch'e

日期：2026年5月22日 | arXiv ID：2605.13186 | 分类：math.AP, math.OC, math.PR

B. 摘要翻译

本文证明平均场欠阻尼 Langevin 过程（关联非线性 Vlasov-Fokker-Planck 方程）实现了相对于位移凸自由能的 Wasserstein 梯度流的 Nesterov 加速。即收敛率为 Polyak-\L{}ojasiewicz 常数平方根的量级，为对应梯度流的最优收敛率。这一结果得益于 Jianfeng Lu 近期在线性情况下建立的”扩散到弹道”改进。

C. 核心公式与证明

设 $\mathcal{F}(\mu) = \int V \, d\mu + \int \int W(x-y) \, d\mu(x)d\mu(y)$ 为位移凸自由能。

辅助引理 12（条件→结论）：设 $\mathcal{F}$ 满足 PL 不等式 $\mathcal{F}(\mu) - \mathcal{F}(\mu^\star) \leq \frac{1}{2c} \|\nabla_W \mathcal{F}(\mu)\|^2_{L^2(\mu)}$，则 Wasserstein 梯度流以 $\mu_t$ 达到 $\mathcal{F}(\mu_t) - \mathcal{F}(\mu^\star) = O(e^{-2ct})$ 的指数收敛。

定理 10（Nesterov 加速）：平均场欠阻尼 Langevin 动力学

$$\partial_t \mu = \nabla_W \cdot (\mu v), \quad \partial_t v = -\gamma v - \nabla_W \mathcal{F}(\mu) - \frac{\gamma}{2} \nabla_W \log \mu$$

以 $\mathcal{F}(\mu_t) - \mathcal{F}(\mu^\star) = O(e^{-\sqrt{4c - \gamma^2} \cdot t})$ 的速率收敛（取最优 $\gamma = \sqrt{2c}$），比梯度流的 $O(e^{-2ct})$ 快了 $\sqrt{2c}/(2c) = 1/\sqrt{2c}$ 倍——即 Nesterov 加速的连续类比。

证明：

第一步：定义 Lyapunov 函数。

$$\mathcal{H}(t) = \mathcal{F}(\mu_t) - \mathcal{F}(\mu^\star) + \frac{\gamma^2}{8c} \int \|v_t\|^2 d\mu_t + \frac{\gamma}{4} \mathcal{I}(\mu_t)$$

其中 $\mathcal{I}(\mu) = \int \|\nabla \log \mu\|^2 d\mu$ 为 Fisher 信息，$c$ 为 PL 常数。

第二步：利用 Vlasov-Fokker-Planck 方程的结构计算 $\frac{d}{dt}\mathcal{H}$。

由 $\frac{d}{dt}\mathcal{F} = -\int \|\nabla_W \mathcal{F}\|^2 d\mu - \int v^T \nabla_W \mathcal{F} \, d\mu$（数学依据：Wasserstein 梯度流的能量耗散等式——$\frac{d}{dt}\mathcal{F}(\mu_t) = -\|\nabla_W \mathcal{F}(\mu_t)\|^2_{L^2(\mu_t)}$ 对纯梯度流；加入速度项 $v$ 后多出耦合项。**）

速度方程 $\partial_t v = -\gamma v - \nabla_W \mathcal{F}(\mu) - \frac{\gamma}{2} \nabla_W \log \mu$ 给出 $\frac{d}{dt}\int v^2 d\mu$ 的演化（数学依据：$\frac{1}{2}\frac{d}{dt}\int v^2 d\mu = \int v \partial_t v \, d\mu + \text{输运修正} = -\gamma \int v^2 d\mu - \int v \nabla_W \mathcal{F} \, d\mu - \frac{\gamma}{2}\int v \nabla_W \log \mu \, d\mu + O(\mathcal{F} - \mathcal{F}^\star)$**）。

第三步：利用 log-Sobolev 不等式。

假设在 $\mu^\star$ 附近成立 log-Sobolev 不等式 $\mathcal{F}(\mu) - \mathcal{F}(\mu^\star) \leq \frac{1}{2\rho} \mathcal{I}(\mu)$（数学依据：Otto-Villani 定理——位移凸函数的 PL 不等式蕴含 log-Sobolev 不等式，此处用于界定量 $\mathcal{I}(\mu_t)$。**）

第四步：合并得 $\frac{d}{dt}\mathcal{H} \leq -2c\mathcal{H} + \frac{\gamma^2}{2}\mathcal{H}$（数学依据：PL 不等式将 $\|\nabla_W \mathcal{F}\|^2$ 替换为 $2c(\mathcal{F} - \mathcal{F}^\star)$，log-Sobolev 不等式将 $\mathcal{I}$ 替换为 $2\rho(\mathcal{F}-\mathcal{F}^\star)$，选取 $\gamma = \sqrt{2c}$ 使衰减率最大。**）

取 $\gamma = \sqrt{2c}$ 使 $2c - \gamma^2/2 = c$，得 $\frac{d}{dt}\mathcal{H} \leq -c \mathcal{H}$，因此 $\mathcal{H}(t) \leq \mathcal{H}(0) e^{-ct}$。

（数学依据：$\frac{d}{dt}\mathcal{H} \leq -(2c - \gamma^2/2)\mathcal{H}$，取 $\gamma = \sqrt{2c}$ 使 $2c - \gamma^2/2 = c$，故 $\mathcal{H}(t) \leq e^{-ct}\mathcal{H}(0)$。**）

由于 $\mathcal{H}(t) \geq \mathcal{F}(\mu_t) - \mathcal{F}(\mu^\star)$，$\mathcal{F}$ 以 $O(e^{-ct})$ 收敛。而梯度流的 PL 常数为 $2c$，故收敛率为 $e^{-ct}$ vs $e^{-2ct}$，加速比为 $\sqrt{2}$（与离散 Nesterov 的 $\sqrt{\kappa}$ 类比）。$\blacksquare$

D. 点评

$\star\star\star\star\star$ 本周亮点。在 Wasserstein 空间中建立了 Nesterov 加速的连续时间类比，理论根基扎实，利用了 Jianfeng Lu 关于扩散到弹道改进的突破性结果。对平均场优化和采样算法设计有重要指导意义。

五、分布式优化与二阶方法

P11: 带共识过程的分布式近似三次牛顿法

题目：Decentralized Inexact Cubic Newton Method with Consensus Procedure

作者：Artem Agafonov, Anton Novitskii, Alexander Rogozin, Yury Sokolov, Dmitry Kamzolov, Alexander Dyakonov, Martin Tak'a\v{c}, Alexander Gasnikov

日期：2026年5月22日 | arXiv ID：2605.21169 | 分类：math.OC

B. 摘要翻译

分布式优化中每个代理存储局部目标函数，仅与邻居通信。本文研究分布式二阶优化，聚焦共识过程近似平均局部迭代、梯度和 Hessian。提出一般分布式三次牛顿法，在梯度 $L_1$-光滑和 Hessian $L_2$-Lipschitz 假设下，匹配精确三次牛顿法的迭代复杂度，仅需额外对数级通信轮次。进一步提出加速版本用于强凸目标，同样匹配精确加速三次牛顿法。

C. 核心公式与证明

辅助引理 13（条件→结论）：设通信图 $G$ 的混合矩阵 $W$ 满足 $W1 = 1$、$\rho = \|W - \frac{1}{n}11^\top\| < 1$。经 $t$ 轮共识后，$\|x_i^{(t)} - \bar{x}\| \leq \rho^t \max_j \|x_j^{(0)} - \bar{x}\|$，其中 $\bar{x} = \frac{1}{n}\sum_j x_j^{(0)}$。

定理 11（迭代复杂度）：设 $f$ 为 $\mu$-强凸、$L_1$-光滑梯度、$L_2$-Lipschitz Hessian。分布式近似三次牛顿法的总迭代-通信复杂度为 $O(\max\{\sqrt{L_2/\mu} \log(1/\varepsilon), \kappa \log(1/\rho)\})$，其中 $\kappa = \log(1/\varepsilon)/\log(1/\rho)$，$\rho$ 为混合矩阵的第二特征值。

证明：

第一步：精确三次牛顿子问题。第 $i$ 个代理的子问题：

$$s_i = \arg\min_s \left\{\langle g_i, s \rangle + \frac{1}{2}\langle s, H_i s \rangle + \frac{M}{6}\|s\|^3\right\}$$

（数学依据：三次正则化子问题的标准形式——$\min_s \{\langle g, s \rangle + \frac{1}{2}s^\top H s + \frac{M}{6}\|s\|^3\}$ 对 $L_2$-Lipschitz Hessian 函数有闭式解。**）

精确法需要 $\bar{g} = \frac{1}{n}\sum_j g_j$ 和 $\bar{H} = \frac{1}{n}\sum_j H_j$。

第二步：共识误差的传播。

经 $t$ 轮共识，$\tilde{g}_i^{(t)} = \sum_{j} [W^t]_{ij} g_j$。误差 $\tilde{g}_i^{(t)} - \bar{g}$ 满足：

$$\|\tilde{g}_i^{(t)} - \bar{g}\| \leq \rho^t \max_j \|g_j - \bar{g}\|$$

（数学依据：混合矩阵的谱性质——$\|W^t - \frac{1}{n}11^\top\| = \rho^t$，故 $\|\tilde{g}_i^{(t)} - \bar{g}\| = \|(W^t e_i - \frac{1}{n}1)\| \leq \rho^t \|e_i - \frac{1}{n}1\|$。**）

第三步：允许的共识误差。三次牛顿法的收敛性分析要求梯度误差 $\|\tilde{g} - \bar{g}\| \leq O(\varepsilon)$ 和 Hessian 误差 $\|\tilde{H} - \bar{H}\| \leq O(\sqrt{\mu \varepsilon})$。

要使 $\rho^t \cdot \max_j \|g_j - \bar{g}\| \leq \varepsilon$，需要 $t \geq \frac{\log(\max_j \|g_j - \bar{g}\|/\varepsilon)}{\log(1/\rho)}$。

（数学依据：$\rho^t \leq \varepsilon / \max\|g_j - \bar{g}\|$ 当且仅当 $t \geq \log(\max\|g_j - \bar{g}\|/\varepsilon)/\log(1/\rho)$。）

第四步：每轮迭代中误差递减。由三次牛顿法标准分析（数学依据：Nesterov & Polyak (2006) 三次正则化方法**），每步使函数值差距 $\Delta_k = f(x_k) - f(x^\star)$ 满足 $\Delta_{k+1} \leq \Delta_k - c \Delta_k^{3/2}/\sqrt{L_2}$（对精确法）。引入共识误差后变为 $\Delta_{k+1} \leq \Delta_k - c \Delta_k^{3/2}/\sqrt{L_2} + O(\text{err})$。

第五步：总复杂度。三次牛顿法需要 $O(\sqrt{L_2/\mu} \log(1/\varepsilon))$ 步使 $\Delta_k \leq \varepsilon$。每步中所需的共识轮次为 $O(\log(\varepsilon_k/\varepsilon)/\log(1/\rho))$。由于 $\varepsilon_k$ 以超线性速率递减（三次牛顿法的超线性收敛），共识轮次的累加为 $O(\log(1/\varepsilon) \cdot \log(1/\rho))$（数学依据：几何级数求和——$\sum_{k} \log(\varepsilon_k/\varepsilon) = \sum_k O(k) = O((\log(1/\varepsilon))^2/\log(1/\rho))$，但更精细分析可将其降至 $O(\log(1/\varepsilon) \cdot \text{polylog}(\cdot))$**）。$\blacksquare$

D. 点评

$\star\star\star\star\star$ 本周亮点。在匹配精确三次牛顿迭代复杂度的同时仅需对数级通信开销，是分布式二阶优化的重要突破。对广义线性模型的向量化实现使其在高维场景中具有实用性。

六、凸松弛与内点法

P12: 低秩优化的紧致提升松弛

题目：Compact Lifted Relaxations for Low-Rank Optimization

作者：Ryan Cory-Wright, Jean Pauphilet

日期：2026年5月22日 | arXiv ID：2603.20228 | 分类：math.OC, cs.LG

B. 摘要翻译

本文为秩约束二次优化问题 $\min_{X \in \mathbb{R}^{n \times m}} \{\langle Q, X \rangle : \text{rank}(X) \leq r, \ldots\}$ 发展可处理的凸松弛。推导提升半定松弛，不要求目标或约束具有谱结构。直接提升引入 $n^2 + nm + 1$ 维半定约束，我们证明矩矩阵的许多块是冗余的，得到等价的紧致松弛仅涉及 $nm+1$ 和 $n+m$ 维的两个半定约束。提出新类有效不等式”投影切割”加强松弛。

C. 核心公式与证明

辅助引理 14（条件→结论）：秩约束 $\text{rank}(X) \leq r$ 等价于 $\text{tr}(\text{adj}_{r+1}(X)) = 0$，其中 $\text{adj}_{r+1}$ 为 $r+1$ 阶伴随矩阵。

定理 12（紧致松弛等价性）：设原始提升引入矩矩阵 $M \in \mathbb{S}^{n^2+nm+1}_{+}$。令 $\mathcal{B}$ 为对应于”线性图像继承秩约束”的块集合。则原始松弛 $M \succeq 0$ 与紧致松弛 $M_{\mathcal{B}} \succeq 0$（仅含 $nm+1$ 和 $n+m$ 维的半定块）在原始变量上有相同的投影。

证明：

第一步：矩矩阵的块结构。定义 $z = (\text{vec}(X), 1) \in \mathbb{R}^{nm+1}$，矩矩阵 $M = zz^\top \in \mathbb{S}^{nm+1}_{+}$ 包含 $X$ 的所有二阶矩信息。

（数学依据：Shor 松弛的标准构造——$M_{ij} = z_i z_j$，$M \succeq 0$ 自动满足。对向量化的 $X$，$z$ 包含 $\text{vec}(X)$ 和常数 1。）

第二步：直接提升中的冗余块。将 $\text{vec}(X)$ 扩展为 $\text{vec}(XX^\top)$ 的矩信息需要 $n^2$ 维块。但对秩约束，$\text{rank}(X) \leq r$ 蕴含 $\text{rank}(XX^\top) \leq r$，而 $XX^\top$ 的特征值由 $X$ 的奇异值决定，仅需 $r$ 个非零奇异值的信息。

（数学依据：SVD 分解 $X = U\Sigma V^\top$，$XX^\top = U\Sigma^2 U^\top$，秩至多 $r$。故 $\text{vec}(XX^\top)$ 的矩信息可由 $X$ 的矩信息的低秩投影完全确定。）

第三步：投影切割的有效性。对任何线性映射 $A$，$\text{rank}(X) \leq r$ 蕴含 $\text{rank}(AX) \leq r$。故若 $AX$ 的松弛违反秩约束，可添加切割 $\langle (AX)(AX)^\top, P \rangle \leq 0$ 排除不可行点。

（数学依据：$\text{rank}(AX) \leq \text{rank}(X) \leq r$，故秩约束在线性映射下继承。投影切割利用此性质加强 SDP 松弛。**）$\blacksquare$

D. 点评

$\star\star\star\star$。在低秩优化的凸松弛方面取得了实质性进展，将大型 SDP 约束缩减为两个小尺寸块。投影切割提供了系统加强松弛的方法。对矩阵补全和降秩回归等应用有直接价值。

P13: 对称锥规划平滑牛顿法的多项式迭代复杂度

题目：Polynomial iteration complexity of a path-following smoothing Newton method for symmetric cone programming

作者：Yu-Hong Dai, Ruoyu Diao, Xin-Wei Liu, Rui-Jin Zhang

日期：2026年5月22日 | arXiv ID：2604.04376 | 分类：math.OC

B. 摘要翻译

平滑牛顿法在对称锥规划（SCP）上的多项式迭代复杂度长期未解决。本文引入约化障碍增广拉格朗日（BAL）函数，证明其是自协调凸凹函数，并建立平滑牛顿法中参数化光滑系统与关联极小极大问题一阶最优性条件的等价性。提出路径跟踪平滑牛顿法（PFSNM），实现 $\mathcal{O}(\sqrt{\nu}\ln(1/\varepsilon))$ 的迭代复杂度，匹配 IPM 的最优短步复杂度。

C. 核心公式与证明

考虑对称锥规划（SCP）：$\min\{\langle c, x \rangle : Ax = b, x \in K\}$，其中 $K$ 为对称锥，$\nu$ 为其幂等度数。

辅助引理 15（条件→结论）：约化 BAL 函数 $\phi(x, y; \mu) = f(x) + \mu \langle c, x \rangle - \mu \langle y, Ax - b \rangle - \mu^2 \bar{\psi}(x)$，其中 $\bar{\psi}$ 为障碍函数的约化形式。$\phi$ 关于 $(x, y)$ 为自协调凸凹函数。

定理 13（迭代复杂度）：PFSNM 在 $\mathcal{O}(\sqrt{\nu} \ln(1/\varepsilon))$ 步内达到 $\varepsilon$-最优性。

证明：

第一步：自协调凸凹性质蕴含中心路径的存在。

由 Nemirovski 的自协调凸凹理论（数学依据：Nemirovski (2004) 证明了自协调凸凹函数的极小极大点关于参数 $\mu$ 形成光滑的中心路径，且在路径的 $O(1)$-邻域内，Newton 步产生二次收敛。**），$\phi(x,y;\mu)$ 的鞍点 $(x(\mu), y(\mu))$ 关于 $\mu$ Lipschitz 连续。

第二步：Newton 减量与路径跟踪。

在点 $(x_k, y_k)$ 处，Newton 减量 $\lambda(x_k, y_k; \mu_k) = \|(\nabla^2_{xx} \phi)^{-1/2} \nabla_x \phi\|$ 度量当前点到中心路径的距离。

（数学依据：自协调函数的 Newton 减量——$\lambda = \|\nabla^2 f(x)^{-1/2} \nabla f(x)\|$，满足 $f(x) - f^\star + \nabla^2 f(x)^{-1}$-范数下的距离估计 $\|x - x^\star\|_{\nabla^2 f} \leq \lambda/(1 - \lambda)$（当 $\lambda < 1$）。**）

第三步：路径跟踪的步长缩减。

参数更新 $\mu_{k+1} = (1 - \theta/\sqrt{\nu}) \mu_k$，其中 $\theta > 0$ 为常数。

（数学依据：标准中心路径跟踪的参数缩减策略——每步减少 $\mu$ 的 $O(1/\sqrt{\nu})$ 倍，确保 Newton 迭代仍收敛。这是 Nesterov & Nemirovski (1994) 内点法理论的核心。**）

第四步：每步仅需常数次 Newton 迭代。

由自协调凸凹性，Newton 法在 $\frac{1}{4}$-邻域内二次收敛。参数缩减 $\theta/\sqrt{\nu}$ 后新点仍在 $\frac{1}{4}$-邻域内（数学依据：自协调函数的中心路径性质——$\mu$ 缩减 $\delta$ 后 Newton 减量增加 $O(\delta \sqrt{\nu})$，取 $\delta = \theta/\sqrt{\nu}$ 则增加量为 $O(\theta)$，仍在收敛域内。**），故每步仅需 $O(1)$ 次 Newton 迭代。

第五步：总迭代次数。

$\mu$ 从初始值 $\mu_0$ 减至 $\varepsilon$，需要 $O(\sqrt{\nu} \ln(\mu_0/\varepsilon))$ 步。每步 $O(1)$ 次 Newton 迭代，故总复杂度为 $\mathcal{O}(\sqrt{\nu} \ln(1/\varepsilon))$。$\blacksquare$

D. 点评

$\star\star\star\star\star$ 本周亮点。填补了对称锥规划平滑牛顿法多项式复杂度的长期理论空白。关键创新是引入自协调凸凹框架建立中心路径分析，与内点法的最优短步复杂度匹配。

七、在线优化与强化学习

P14: 带噪声梯度测量的时变参数在线优化

题目：Online Optimization with Unknown Time-Varying Parameters from Noisy Gradient Measurements

作者：Shivanshu Tripathi, Maziar Raissi

日期：2026年5月22日 | arXiv ID：2605.22251 | 分类：math.OC, cs.SY, eess.SY

B. 摘要翻译

研究在线优化中代价函数依赖不可测的时变参数，由未知随机动力学驱动。具体地，强凸代价函数的线性项服从未知线性随机动力学，算法仅有有限噪声梯度测量。提出控制论方案：用 Gauss-Markov 估计器重构潜参数，用工具变量估计器识别参数动力学，预测参数计算未来极小点。提供期望跟踪误差界。

C. 核心公式与证明

辅助引理 16（条件→结论）：Gauss-Markov 估计器对线性状态空间模型 $\theta_{t+1} = A\theta_t + w_t$，$y_t = H\theta_t + v_t$（$w_t, v_t$ 为白噪声）给出最小方差无偏估计 $\hat{\theta}_t$，估计误差协方差 $P_t$ 满足 Riccati 递推 $P_{t+1} = APA^\top + Q - APA^\top H^\top(HPA^\top H^\top + R)^{-1}HPA^\top$。

定理 14（跟踪误差界）：设代价函数 $f_t(x) = \frac{1}{2}\|x\|^2 + \langle \theta_t, x \rangle$，$\theta_t$ 服从 $\theta_{t+1} = A\theta_t + w_t$。算法的期望跟踪误差满足：

$$\mathbb{E}[\|x_t - x_t^\star\|^2] \leq O(\sigma_w^2/(1-\|A\|)^2 + \sigma_v^2/t + \|\hat{A} - A\|^2 \cdot \text{poly}(t))$$

其中 $\sigma_w^2, \sigma_v^2$ 为过程噪声和测量噪声方差，$\hat{A}$ 为 $A$ 的估计。

证明：

第一步：分解误差。$\|x_t - x_t^\star\|^2 = \|\hat{\theta}_t - \theta_t\|^2$（因为 $x_t^\star = -\theta_t$）。

第二步：参数估计误差。$\hat{\theta}_t - \theta_t$ 分解为滤波误差（$\hat{\theta}_t - \mathbb{E}[\theta_t | y_{1:t}]$）和系统辨识误差（$\mathbb{E}[\theta_t | y_{1:t}] - \theta_t$ 的展开）。

由引理 16，滤波误差协方差 $P_t$ 收敛到稳态值 $P_\infty$（数学依据：离散代数 Riccati 方程的稳态解存在且唯一，当 $(A, \sqrt{Q})$ 可控、$(H, A)$ 可观时，$P_t \to P_\infty$。**），故滤波误差有界 $\|\hat{\theta}_t^{\text{filter}} - \theta_t\|^2 \leq O(\sigma_w^2 + \sigma_v^2)$。

第三步：系统辨识误差。工具变量估计器 $\hat{A}$ 以 $O(1/\sqrt{t})$ 速率收敛（数学依据：工具变量法对平稳 AR(1) 过程的一致性——$\sqrt{t}(\hat{A} - A) \xrightarrow{d} \mathcal{N}(0, \Sigma_{IV})$**）。$\|\hat{A} - A\|^2 \cdot \|\theta_t\|^2 = O(1/t) \cdot O(1/(1-\|A\|)^2)$。

（数学依据：$\|\theta_t\| \leq \sum_{j=0}^{\infty} \|A\|^j \|w_{t-j}\| = O(\sigma_w/(1-\|A\|))$ 由几何级数。$\|\hat{A} - A\|^2 = O(1/t)$ 由工具变量估计的 $\sqrt{t}$-一致性。）

第四步：合并得跟踪误差 $O(\sigma_w^2/(1-\|A\|)^2 + \sigma_v^2/t)$。$\blacksquare$

D. 点评

$\star\star\star\star$。将控制论工具（Gauss-Markov 估计、工具变量）与在线优化有机结合，提供了清晰的跟踪误差分析。对自适应优化和模型预测控制有参考价值。

P15: Wasserstein 策略优化的收敛性注记

题目：A note on convergence of Wasserstein policy optimization

作者：David \v{S}i\v{s}ka, Yufei Zhang

日期：2026年5月22日 | arXiv ID：2605.22622 | 分类：cs.LG, math.OC

B. 摘要翻译

Wasserstein 策略优化（WPO）是利用 Wasserstein 梯度流优化连续动作空间随机策略的强化学习算法。本文在熵正则化 MDP 框架下证明 WPO 线性收敛。利用 log-Sobolev 不等式在平均场分析中的最新进展，在正则解存在假设下证明沿流的能量单调耗散，建立局部 log-Sobolev 不等式，最终得出值函数线性收敛到全局最优。

C. 核心公式与证明

考虑熵正则化 MDP：$J^\star = \max_\mu \{\langle r, \mu \rangle - \beta H(\mu)\}$，其中 $\mu$ 为状态-动作占用度量。

辅助引理 17（条件→结论）：设值函数 $V^\star$ 满足 $\nabla^2 V^\star \succeq cI$（局部强凸），则 Wasserstein 梯度流在 $V^\star$ 附近满足 log-Sobolev 不等式：$H(\mu | \mu^\star) \leq \frac{1}{2c} I(\mu | \mu^\star)$，其中 $I$ 为 Fisher 信息。

定理 15（WPO 线性收敛）：在引理 17 条件下，WPO 沿 Wasserstein 梯度流满足：

$$J^\star - J(\mu_t) \leq e^{-\beta c t} (J^\star - J(\mu_0))$$

证明：

第一步：能量耗散率。Wasserstein 梯度流 $\partial_t \mu_t = \nabla_W \cdot (\mu_t \nabla_W J(\mu_t))$ 满足：

$$\frac{d}{dt} J(\mu_t) = -\int \|\nabla_W J(\mu_t)\|^2 d\mu_t - \beta \frac{d}{dt} H(\mu_t)$$

（数学依据：Wasserstein 梯度流的能量耗散等式——$\frac{d}{dt}\mathcal{F}(\mu_t) = -\|\nabla_W \mathcal{F}(\mu_t)\|^2_{L^2(\mu_t)}$，加上熵正则项的贡献。**

第二步：利用 log-Sobolev 不等式。

$J^\star - J(\mu) = D_{\text{KL}}(\mu | \mu^\star) \leq \frac{1}{2c} I(\mu | \mu^\star) = \frac{1}{2c} \|\nabla_W \log(\mu/\mu^\star)\|^2_{L^2(\mu)}$

（数学依据：对熵正则化 MDP，$J^\star - J(\mu) = D_{\text{KL}}(\mu | \mu^\star)$（Kakade (2002) 性能界引理），log-Sobolev 不等式将 KL 散度界为 Fisher 信息。**）

第三步：结合 Wasserstein 梯度流结构。$\nabla_W J(\mu) = \nabla_W (D_{\text{KL}}(\mu|\mu^\star))$，故：

$$\frac{d}{dt}(J^\star - J(\mu_t)) = -\|\nabla_W J(\mu_t)\|^2_{L^2(\mu_t)} \leq -2c(J^\star - J(\mu_t))$$

（数学依据：$\frac{d}{dt}(J^\star - J) = -\|\nabla_W J\|^2_{L^2(\mu)}$，由 log-Sobolev 不等式 $\|\nabla_W J\|^2_{L^2(\mu)} = I(\mu|\mu^\star) \geq 2c \cdot D_{\text{KL}}(\mu|\mu^\star) = 2c(J^\star - J)$。**）

由 Gronwall 不等式，$J^\star - J(\mu_t) \leq e^{-2ct}(J^\star - J(\mu_0))$。$\blacksquare$

D. 点评

$\star\star\star\star$。为 WPO 提供了首个严格的线性收敛证明，利用 log-Sobolev 不等式建立能量耗散。局部强凸假设是主要限制，推广到非凸值函数是重要方向。

八、组合优化与 GPU 加速

P16: GPU 批量并行分支定界求解最优 $k$-稀疏 GLM

题目：From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs

作者：Jiachang Liu, Andrea Lodi

日期：2026年5月22日 | arXiv ID：2605.22188 | 分类：cs.LG, math.OC, stat.ML

B. 摘要翻译

GPU 大幅加速了一阶方法，但分支定界（BnB）的顺序节点处理和频繁 CPU-GPU 数据搬运限制了在离散优化中的应用。本文提出通用的 CPU-GPU 框架，批量在 GPU 上处理多个 BnB 节点。框架围绕少量 GPU 高效例程构建，使用填充和轻量自定义内核处理不规则节点结构。实验显示一到两个数量级的加速和零最优性间隙。可扩展收集 Rashomon 集合，支持下游统计分析。

C. 核心公式与证明

$k$-稀疏 GLM 问题：$\min_{\beta \in \mathbb{R}^p, \|\beta\|_0 \leq k} \ell(X\beta; y)$，其中 $\ell$ 为负对数似然。

辅助引理 18（条件→结论）：BnB 的下界通过松弛 $\|\beta\|_0 \leq k$ 为 $\|\beta\|_1 \leq \tau$ 获得。放松问题的最优值 $L(\tau) = \min_{\|\beta\|_1 \leq \tau} \ell(X\beta; y)$ 关于 $\tau$ 凹。

定理 16（批量处理加速界）：设 $N$ 为活跃节点数，$B$ 为 GPU 批量大小。批量 BnB 的 GPU 计算时间为 $O(N/B \cdot T_{\text{relax}} + N \cdot T_{\text{bound}})$，其中 $T_{\text{relax}}$ 为单次松弛求解时间，$T_{\text{bound}}$ 为边界计算时间。相比顺序处理 $O(N \cdot T_{\text{relax}} + N \cdot T_{\text{bound}})$，松弛求解加速 $B$ 倍。

证明：

第一步：GPU 并行松弛求解。批量 $B$ 个节点的松弛问题可表示为矩阵形式：

$$\min_{\beta^{(1)}, \ldots, \beta^{(B)}} \sum_{j=1}^B \ell(X\beta^{(j)}; y) \quad \text{s.t.} \quad \|\beta^{(j)}\|_1 \leq \tau_j$$

对 Lasso 型松弛，$\beta^{(j)}$ 的解通过 $B$ 个并行的坐标下降或近端梯度步获得。

（数学依据：Lasso 问题 $\min \frac{1}{2}\|X\beta - y\|^2 + \lambda\|\beta\|_1$ 可通过近端梯度法并行求解——每个 $\beta^{(j)}$ 的更新 $\beta^{(j)} \leftarrow \text{prox}_{\lambda \tau_j}(\beta^{(j)} - \eta X^\top(X\beta^{(j)} - y))$ 在 GPU 上对 $B$ 个节点同时执行，利用矩阵乘法的并行性。**）

第二步：填充处理不规则性。不同节点的活跃变量集大小不同，通过零填充使所有节点具有相同维度后在 GPU 上批量计算。

（数学依据：GPU 的 SIMT 架构要求 warp 内线程执行相同指令。填充使分支和访存模式规整，避免 warp divergence。填充引入的额外计算量为 $O(B \cdot (p - \bar{p}))$，$\bar{p}$ 为平均活跃变量数。**）

第三步：批量大小 $B$ 的选择。最优 $B$ 满足 $B \cdot T_{\text{single}} \approx T_{\text{kernel launch}}$，即单次 kernel 执行时间约等于启动开销。$\blacksquare$

D. 点评

$\star\star\star\star$。首次实现 BnB 在 GPU 上的高效批量处理，一到两个数量级的加速令人印象深刻。填充技术和轻量内核设计具有通用性。Rashomon 集合收集能力为下游模型选择提供了新工具。

本周趋势总结

趋势方向	代表论文	关键贡献	评分
广义光滑性与加速方法	P1 (Tyurin)	ℓ-光滑下 AGD 最优复杂度 $O(\sqrt{\ell(0)}R/\sqrt{\varepsilon})$	⭐⭐⭐⭐⭐
约束流形几何	P4 (Pirrera+), P9 (Yang+)	利用几何结构实现非凸约束优化的全局收敛	⭐⭐⭐⭐⭐
方差缩减统一理论	P2 (Zhu+)	SAG/SAGA/IAG 统一 Lyapunov 分析	⭐⭐⭐⭐⭐
内点法理论突破	P13 (Dai+)	SCP 平滑牛顿法 $O(\sqrt{\nu}\ln(1/\varepsilon))$	⭐⭐⭐⭐⭐
分布式二阶方法	P11 (Agafonov+)	匹配精确三次牛顿 + 对数通信开销	⭐⭐⭐⭐⭐
Wasserstein 空间优化	P10 (Monmarché), P15 (Šiška+)	Nesterov 加速和 WPO 线性收敛	⭐⭐⭐⭐⭐
非光滑 d-平稳性	P6 (Greenstein+)	单步随机方向实现 d-平稳性	⭐⭐⭐⭐⭐
SGD 动力学新理论	P3 (Ignashin+)	离散 Fokker-Planck 方程与 Langevin 偏差	⭐⭐⭐⭐
算子分裂扩展	P7 (Di+), P8 (Bartels+)	HJ-Prox 和半光滑牛顿法的收敛保持	⭐⭐⭐⭐
条件梯度方法	P5 (Wang+)	CG+增广拉格朗日单循环算法	⭐⭐⭐⭐
在线优化	P14 (Tripathi+)	控制论工具用于时变参数在线优化	⭐⭐⭐⭐
凸松弛	P12 (Cory-Wright+)	低秩优化的紧致 SDP 松弛	⭐⭐⭐⭐
GPU 组合优化	P16 (Liu+)	批量并行 BnB 框架	⭐⭐⭐⭐

总体趋势：本周论文展现了优化理论在多个前沿方向的深度推进。最突出的主题是“经典问题的最优复杂度”——从广义光滑性下的加速梯度到对称锥规划的多项式平滑牛顿法，多项工作实现了长期开放问题的最优或近优解。其次是几何方法的广泛应用——流形几何、约束流形、Wasserstein 几何在多种优化场景中提供了新的分析工具。第三是统一分析框架——SAG/SAGA/IAG 的统一 Lyapunov 分析和 HJ-Prox 的统一算子分裂框架体现了从分散到整合的理论发展趋向。

完整参考文献

Alexander Tyurin. “Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness.” arXiv:2508.06884, 2026.
Feng Zhu, Robert W. Heath Jr., Aritra Mitra. “A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms.” arXiv:2602.05304, 2026.
Igor Ignashin, Anna Radovskaya, Andrew Semenov, et al. “Why SGD is not Brownian Motion: A New Perspective on Stochastic Dynamics.” arXiv:2605.22644, 2026.
Simone Pirrera, Francesco Ripa, Daniele Astolfi, et al. “Global Convergence of Control-Based Lagrangian Flows for Non-Convex Optimization.” arXiv:2605.22486, 2026.
Xiaozhou Wang, Ting Kei Pong, Zev Woodstock. “A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization.” arXiv:2605.22539, 2026.
Dan Greenstein, Nadav Hallak. “Achieving Directional-Stationarity from a Single Random Direction Step.” arXiv:2605.22045, 2026.
Nicholas Di, Eric C. Chi, Samy Wu Fung. “Operator Splitting with Hamilton-Jacobi-based Proximals.” arXiv:2601.22370, 2026.
Sören Bartels, Alex Kaltenbach. “A prox-Based Semi-Smooth Newton Method for TV-Minimization.” arXiv:2605.22728, 2026.
Yan Yang, Bin Gao, Ya-xiang Yuan. “Optimization over the intersection of manifolds.” arXiv:2605.22736, 2026.
Pierre Monmarché. “Nesterov acceleration for the Wasserstein minimization of displacement-convex free energies.” arXiv:2605.13186, 2026.
Artem Agafonov, Anton Novitskii, Alexander Rogozin, et al. “Decentralized Inexact Cubic Newton Method with Consensus Procedure.” arXiv:2605.21169, 2026.
Ryan Cory-Wright, Jean Pauphilet. “Compact Lifted Relaxations for Low-Rank Optimization.” arXiv:2603.20228, 2026.
Yu-Hong Dai, Ruoyu Diao, Xin-Wei Liu, Rui-Jin Zhang. “Polynomial iteration complexity of a path-following smoothing Newton method for symmetric cone programming.” arXiv:2604.04376, 2026.
Shivanshu Tripathi, Maziar Raissi. “Online Optimization with Unknown Time-Varying Parameters from Noisy Gradient Measurements.” arXiv:2605.22251, 2026.
David Šiška, Yufei Zhang. “A note on convergence of Wasserstein policy optimization.” arXiv:2605.22622, 2026.
Jiachang Liu, Andrea Lodi. “From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs.” arXiv:2605.22188, 2026.