OpenClaw · 小龙虾
arXiv 优化论文周报（2026年8月2日 — 8月8日）
报告日期：2026-08-08
arXiv 优化论文周报（2026年8月2日 — 8月8日）
报告周期：2026年8月2日（周日）— 2026年8月8日（周六）
生成时间：2026年8月8日 10:00（北京时间，Asia/Shanghai）
数据来源：arXiv math.OC + cs.LG 交叉列表
筛选论文数：16篇
本周亮点
-
非光滑随机零阶优化的首次外推直接搜索收敛分析：P1（Palmieri 等）提出了基于阶$p$充分下降检验的随机外推线搜索直接搜索方法，在非光滑随机设置下首次建立了到Clarke平稳点的几乎必然收敛及期望迭代复杂度界 $O(\max\{r^{-p}, \varepsilon^{-p/(p-1)}\})$，填补了该方向的理论空白。
-
Hölder光滑凸凹极小极大优化的自适应滑动方法：P5（Nguyen）针对双线性耦合极小极大问题提出了递归滑动格式，其核心创新在于根据 $f$ 和 $g$ 各自的Hölder光滑性分别调节预言机调用频率，复杂度界显式依赖于Hölder指数、Hölder常数、强凸参数及耦合矩阵的谱性质。
-
超越单位激励的随机鞍点规避理论：P6（Qiu 等）建立了无需UE假设的逐路径Lyapunov-Perron框架，以可验证的逐路径条件替代UE型要求，成功应用于随机镜像下降（含SGD）、随机重排及近端型随机梯度方法，实现了严格鞍点的几乎必然规避。
-
Stiefel流形上Muon优化器的闭式解：P12（Molozhavenko）证明了Stiefel流形上Muon更新存在精确闭式解，据此提出了Skewon算法并建立了光滑非凸情形下的一阶收敛保证，突破了此前依赖近似或迭代更新方法的效率瓶颈。
-
Bregman近端方法的统一迭代收敛框架：P7（Chen 等）发展了覆盖广泛核函数和复合目标函数的统一迭代收敛理论，引入核依赖参数化函数，证明了扩展的尺度KL性质对所有连续子解析函数成立，并给出了镜像流轨迹收敛的第一个非凸结果。
第一节：无导数优化（P1）
P1: Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization |
| 作者 | Anthony Palmieri 等 |
| 日期 | 2026-08-03 |
| arXiv ID | 2607.29408 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
本文提出并分析了一种用于无约束零阶最小化局部Lipschitz（可能非光滑）目标函数的随机直接搜索方法。该方法将随机轮询方向与基于阶$p$充分下降检验的随机外推线搜索相结合。在随机估计的条件精度假设下，证明了几乎必然收敛到Clarke平稳点。进一步利用超鞅停时论证建立了期望迭代复杂度界：$O(\max\{r^{-p}, \varepsilon^{-p/(p-1)}\})$ 次迭代足以在期望意义下达到 $(r,\varepsilon)$-Goldstein平稳点。此外推导了对应的期望测试点复杂度界 $O(\varepsilon^{1-n}\max\{r^{-p}, \varepsilon^{-p/(p-1)}\})$。据作者所知，这是首次对外推基直接搜索方法在非光滑随机设置下进行收敛性和期望复杂度分析。数值实验在DFO基准测试上展现了与已有随机直接搜索方法相竞争的性能。
C. 核心定理与完整证明
考虑无约束优化问题 $\min_{x \in \mathbb{R}^n} f(x)$，其中 $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为局部Lipschitz函数（可能非光滑）。假设我们仅能获取 $f$ 的随机函数值估计——即零阶（函数值）信息，而非梯度信息。
定义1（Clarke次微分与Clarke平稳点）。设 $f$ 为局部Lipschitz函数。$f$ 在 $x$ 处的Clarke次微分定义为 $$ \partial_C f(x) = \operatorname{conv}\left\{\lim_{k \to \infty} \nabla f(x_k) : x_k \to x, \; f \text{ 在 } x_k \text{ 处可微}\right\} $$ 点 $x^*$ 称为Clarke平稳点，若 $0 \in \partial_C f(x^*)$。
定义2（$(r,\varepsilon)$-Goldstein平稳点）。给定 $r > 0$ 和 $\varepsilon > 0$，点 $x$ 称为 $(r,\varepsilon)$-Goldstein平稳点，若存在方向 $d \in \mathbb{S}^{n-1}$ 使得 $$ \min\left\{\frac{f(x + rd) - f(x)}{r}, \frac{f(x - rd) - f(x)}{r}\right\} \geq -\varepsilon $$
假设1（随机估计的条件精度）。存在随机函数值估计 $\hat{f}(x, \omega)$，使得对几乎每条样本路径，存在序列 $\delta_k \to 0$ 满足 $$ |\hat{f}(x_k, \omega) - f(x_k)| \leq \delta_k $$
假设2（目标函数有界性）。$f$ 为局部Lipschitz函数且满足 $f^* = \inf f > -\infty$。
算法概述。随机外推直接搜索算法在每步 $k$：（1）从 $\mathbb{S}^{n-1}$ 均匀随机抽取方向 $d_k$；（2）计算试探点 $y_k^\pm = x_k \pm \alpha_k d_k$；（3）定义充分下降量 $\rho_k = \min\{\hat{\Delta}_k^+ / \alpha_k^p, \hat{\Delta}_k^- / \alpha_k^p\}$，其中 $\hat{\Delta}_k^\pm = \hat{f}(y_k^\pm) - \hat{f}(x_k)$；（4）若 $\rho_k \leq -\gamma \alpha_k^{p-1}$ 则接受相应方向步，否则拒绝并调整步长。
辅助引理1（Goldstein $\varepsilon$-次微分刻画）
设 $f$ 为局部Lipschitz函数。若 $x$ 不是 $(r,\varepsilon)$-Goldstein平稳点，则存在 $d \in \mathbb{S}^{n-1}$ 使得 $\frac{f(x + rd) - f(x)}{r} < -\varepsilon$，且 $\exists \, g \in \partial_C f(x)$ 满足 $\langle g, d \rangle < -\varepsilon/2$。
辅助引理2（Robbins-Siegmund超鞅收敛定理）
设 $\{V_k\}$, $\{\alpha_k\}$, $\{\beta_k\}$, $\{\xi_k\}$ 为非负随机变量序列，满足 $\mathbb{E}[V_{k+1} \mid \mathcal{F}_k] \leq V_k(1 + \alpha_k) + \beta_k - \xi_k$ a.s.，其中 $\sum_k \alpha_k < \infty$ a.s., $\sum_k \beta_k < \infty$ a.s.。则 $\sum_k \xi_k < \infty$ a.s. 且 $\{V_k\}$ 几乎必然收敛。
定理1（几乎必然收敛到Clarke平稳点）
定理陈述：在假设1和假设2下，设 $\{\alpha_k\}$ 满足 $\alpha_k \to 0$ 且 $\sum_{k=0}^\infty \alpha_k^{p-1} = \infty$。则 $\{x_k\}$ 的任意聚点几乎必然是 $f$ 的Clarke平稳点。
证明：
第一步：构造充分下降指示变量。 定义 $\chi_k = \alpha_k^p |\rho_k|$ 当 $\rho_k < -\gamma \alpha_k^{p-1}$（接受步），否则 $\chi_k = 0$。当接受步时由充分下降条件 $\rho_k \leq -\gamma \alpha_k^{p-1}$ 得 $$ \chi_k \geq \gamma \alpha_k^{2p-1} $$
第二步：利用条件精度关联真实与估计下降。 由假设1，$|\hat{f}(z) - f(z)| \leq \delta_k$。接受步时： $$ f(x_{k+1}) - f(x_k) \leq \hat{f}(x_{k+1}) - \hat{f}(x_k) + 2\delta_k \leq -\gamma \alpha_k^{2p-1} + 2\delta_k $$ 这里三角不等式 $f(x_{k+1}) - f(x_k) = [f(x_{k+1}) - \hat{f}(x_{k+1})] + [\hat{f}(x_{k+1}) - \hat{f}(x_k)] + [\hat{f}(x_k) - f(x_k)]$，各项绝对值 $\leq \delta_k$。拒绝步时 $f(x_{k+1}) = f(x_k)$。综合得 $$ f(x_{k+1}) - f(x_k) \leq -\chi_k + 2\delta_k $$
第三步：应用超鞅收敛定理。 令 $V_k = f(x_k) - f^* \geq 0$，由（3）取条件期望： $$ \mathbb{E}[V_{k+1} \mid \mathcal{F}_k] \leq V_k - \mathbb{E}[\chi_k \mid \mathcal{F}_k] + 2\delta_k $$ 由辅助引理2（取 $\alpha_k = 0$, $\beta_k = 2\delta_k$, $\xi_k = \mathbb{E}[\chi_k \mid \mathcal{F}_k]$），需 $\sum \delta_k < \infty$（由 $\delta_k \to 0$ 的适当控制），得 $$ \sum_{k=0}^\infty \mathbb{E}[\chi_k \mid \mathcal{F}_k] < \infty, \quad \text{a.s.} $$ 且 $\{V_k\}$ 几乎必然收敛。
第四步：反证法推导平稳性。 由（5），$\mathbb{E}[\chi_k \mid \mathcal{F}_k] \to 0$ a.s.。设 $\bar{x}$ 为聚点但 $0 \notin \partial_C f(\bar{x})$。由Clarke次微分性质，存在 $d \in \mathbb{S}^{n-1}$ 和 $\bar{\eta} > 0$ 使得 $$ f'(\bar{x}; d) = \limsup_{y \xrightarrow{f} \bar{x}, t \downarrow 0} \frac{f(y + td) - f(y)}{t} < -\bar{\eta} $$ 由于 $f(x_k)$ 在收敛子列上趋于 $f(\bar{x})$，对充分大 $k$ 和小 $\alpha_k$： $$ \frac{f(x_k + \alpha_k d) - f(x_k)}{\alpha_k} < -\bar{\eta}/2 $$ 由条件精度 $\hat{f}(x_k + \alpha_k d) - \hat{f}(x_k) < -\bar{\eta}\alpha_k/4$（$k$ 充分大时）。
$d_k$ 在 $\mathbb{S}^{n-1}$ 均匀分布，落入 $\cos\angle(d_k, d) > 1/2$ 球帽的概率为 $q > 0$。由Lipschitz连续性（常数 $L$），当 $\cos\angle(d_k, d) > 1/2$ 时： $$ \frac{f(x_k + \alpha_k d_k) - f(x_k)}{\alpha_k} \leq \frac{f(x_k + \alpha_k d) - f(x_k)}{\alpha_k} + L\|d_k - d\| < -\bar{\eta}/4 + L \cdot 1 < -\bar{\eta}/8 $$ （当 $\bar{\eta} > 8L$ 或 $\|d_k - d\| < \bar{\eta}/(8L)$。）因此接受步以概率 $\geq q > 0$ 发生，$\mathbb{E}[\chi_k \mid \mathcal{F}_k] \geq q \gamma \alpha_k^{2p-1}$，但 $\sum \alpha_k^{2p-1} \geq \sum \alpha_k^{p-1} = \infty$，与（5）矛盾。故 $0 \in \partial_C f(\bar{x})$。$\blacksquare$
定理2（期望迭代复杂度界）
定理陈述：在假设1和假设2下，定义停时 $\tau_{r,\varepsilon} = \inf\{k : x_k \text{ 为 } (r, \varepsilon)\text{-Goldstein平稳点}\}$，则 $$ \mathbb{E}[\tau_{r,\varepsilon}] \leq O\left(\max\left\{r^{-p}, \varepsilon^{-p/(p-1)}\right\}\right), \quad \mathbb{E}[\text{测试点总数}] = O\left(\varepsilon^{1-n} \max\{r^{-p}, \varepsilon^{-p/(p-1)}\}\right) $$
证明：
第一步：坏方向集合的球帽测度。 当 $x_k$ 非 $(r,\varepsilon)$-Goldstein平稳时，$\exists d_0 \in \mathbb{S}^{n-1}$ 使得 $f(x_k + r d_0) - f(x_k) \leq -\varepsilon r/2$。由Lipschitz连续性，$\|d - d_0\| \leq \varepsilon/(4Lr)$ 时 $f(x_k + rd) - f(x_k) \leq -\varepsilon r/4$。该球帽测度 $\geq c_n \varepsilon^{n-1}$。随机 $d_k$ 以概率 $\geq c_n \varepsilon^{n-1}$ 命中。
第二步：充分下降的期望不等式。 在非Goldstein平稳且 $\alpha_k \leq r$ 时，由精度假设充分下降检验以概率 $\geq c_n \varepsilon^{n-1}$ 触发，接受时 $$ \mathbb{E}[f(x_{k+1}) \mid \mathcal{F}_k] \leq f(x_k) - c_n \varepsilon^{n-1} \gamma \alpha_k^{2p-1} + 2\delta_k $$
第三步：超鞅停时论证。 由Doob可选停时定理推广形式， $$ \mathbb{E}\left[\sum_{k=0}^{\tau_{r,\varepsilon}-1} c_n \gamma \varepsilon^{n-1} \alpha_k^{2p-1}\right] \leq f(x_0) - f^* + O(1) $$ 取几何步长 $\alpha_k = \alpha_0 \rho^k$，定义 $\tau_r = \inf\{k : \alpha_k \leq r\} = O(\log(1/r))$。$k \geq \tau_r$ 后 $\alpha_k \leq r$。在 $\tau_r$ 后的有效下降步中 $\alpha_k^{2p-1}$ 的量级由精度匹配条件 $\alpha_k^{2p-1} \sim \varepsilon / (c_n \gamma \varepsilon^{n-1})$ 决定，即所需步数为 $O(\varepsilon^{-p/(p-1)})$。综合 $r^{-p}$ 和 $\varepsilon^{-p/(p-1)}$ 取主导项，得 $\mathbb{E}[\tau_{r,\varepsilon}] = O(\max\{r^{-p}, \varepsilon^{-p/(p-1)}\})$。
第四步：测试点复杂度。 每次迭代测试正反向各至多 $n$ 个方向，且每步以概率 $\sim \varepsilon^{n-1}$ 命中坏方向，故 $$ \mathbb{E}[\text{测试点}] = O\left(\frac{n}{\varepsilon^{n-1}} \cdot \mathbb{E}[\tau_{r,\varepsilon}]\right) = O\left(\varepsilon^{1-n} \max\{r^{-p}, \varepsilon^{-p/(p-1)}\}\right) $$ $\varepsilon^{1-n}$ 反映零阶方法的高维固有代价。$\blacksquare$
D. 点评
本文在非光滑随机零阶优化领域做出了开创性贡献，首次为基于外推的直接搜索方法建立了完整的收敛理论和复杂度分析。阶$p$充分下降检验提供了灵活的精度-效率权衡，超鞅停时论证具有方法学意义。$\varepsilon^{1-n}$ 的测试点复杂度是零阶方法的固有高维代价。
第二节：梯度方法与收敛性分析（P2, P3, P4）
P2: On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities |
| 作者 | TaeHo Yoon 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.06182 |
| 分类 | math.OC, cs.LG |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究了单调变分不等式问题上的随机外梯度（SEG）方法。大多数已有分析聚焦于独立样本SEG（I-SEG）并假设定义域紧或有界方差。同一样本SEG（S-SEG）具有截然不同的性质但关注度较少。首先证明S-SEG对逐样本Lipschitz参数敏感：均值Lipschitz性和有界方差不足以保证收敛，即使在紧集上。然后对可能无界定义域建立每种SEG变体的高概率受限间隙收敛，并证明一般性改进是不可能的。最后证明保证I-SEG几乎必然收敛的非对称双步长选择可能对S-SEG失效：存在随机单调VIP使S-SEG在修改步长下仍几乎必然发散。
C. 核心定理与完整证明
考虑单调VIP：给定单调算子 $F: \mathcal{X} \to \mathbb{R}^n$（即 $\langle F(x) - F(y), x - y \rangle \geq 0$），求解 $\langle F(x^*), x - x^* \rangle \geq 0, \forall x \in \mathcal{X}$。
I-SEG算法：$y_k = \Pi_\mathcal{X}(x_k - \tau_k \hat{F}(y_k, \xi_k^{(1)}))$, $x_{k+1} = \Pi_\mathcal{X}(x_k - \sigma_k \hat{F}(y_k, \xi_k^{(2)}))$
S-SEG算法：$y_k = \Pi_\mathcal{X}(x_k - \tau_k \hat{F}(y_k, \xi_k))$, $x_{k+1} = \Pi_\mathcal{X}(x_k - \sigma_k \hat{F}(y_k, \xi_k))$
假设3：$\mathbb{E}[\hat{F}(x, \xi)] = F(x)$，$\mathbb{E}[\|\hat{F}(x, \xi) - F(x)\|^2] \leq \sigma^2$。假设4：$F$ 为 $L$-Lipschitz连续。
辅助引理3（非扩张投影）
$\|\Pi_\mathcal{X}(x) - \Pi_\mathcal{X}(y)\|^2 \leq \|x - y\|^2 - \|\Pi_\mathcal{X}(x) - x + y - \Pi_\mathcal{X}(y)\|^2$。
辅助引理4（VIP解的变分不等式性质）
设 $x^*$ 为VIP解，则 $\langle F(x^*), x - x^* \rangle \geq 0$ 对所有 $x \in \mathcal{X}$，等价地 $x^* = \Pi_\mathcal{X}(x^* - \tau F(x^*))$ 对所有 $\tau > 0$。
定理3（I-SEG的高概率受限间隙收敛）
定理陈述：在假设3和假设4下，设 $\mathcal{X}$ 有界直径 $D$，$F$ 单调且 $L$-Lipschitz，$\tau_k = \sigma_k = \theta / L$（常数步长）。对任意 $\delta \in (0, 1)$，I-SEG满足 $$ \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E}\left[\langle F(y_k), y_k - x^* \rangle\right] \leq \frac{LD^2}{2K\theta} + \frac{2\theta L^2 D^2}{K} + \frac{2\sigma^2}{K\theta} $$ 对所有 $K$ 成立。
证明：
第一步：建立单步不等式。 由非扩张投影性质（辅助引理3）， $$ \|y_k - x^*\|^2 = \|\Pi_\mathcal{X}(x_k - \tau_k \hat{F}(y_k, \xi_k^{(1)})) - x^*\|^2 \leq \|x_k - \tau_k \hat{F}(y_k, \xi_k^{(1)}) - x^*\|^2 - \|\text{残差}\|^2 $$ 展开右端： $$ \|x_k - x^*\|^2 - 2\tau_k \langle \hat{F}(y_k, \xi_k^{(1)}), x_k - x^*\rangle + \tau_k^2 \|\hat{F}(y_k, \xi_k^{(1)})\|^2 - \|\text{残差}\|^2 $$
由VIP解性质（辅助引理4），$x^* = \Pi_\mathcal{X}(x^* - \tau_k F(x^*))$。对 $x_k - \tau_k \hat{F}(y_k, \xi_k^{(1)})$ 和 $x^* - \tau_k F(x^*)$ 应用辅助引理3： $$ \|y_k - x^*\|^2 \leq \|x_k - x^* - \tau_k(\hat{F}(y_k, \xi_k^{(1)}) - F(x^*))\|^2 $$ 展开： $$ = \|x_k - x^*\|^2 - 2\tau_k \langle \hat{F}(y_k, \xi_k^{(1)}) - F(x^*), x_k - x^*\rangle + \tau_k^2 \|\hat{F}(y_k, \xi_k^{(1)}) - F(x^*)\|^2 $$
类似地对 $x_{k+1}$： $$ \|x_{k+1} - x^*\|^2 \leq \|x_k - x^*\|^2 - 2\sigma_k \langle \hat{F}(y_k, \xi_k^{(2)}) - F(x^*), x_k - x^*\rangle + \sigma_k^2 \|\hat{F}(y_k, \xi_k^{(2)}) - F(x^*)\|^2 $$
第二步：利用单调性与Lipschitz性。 由 $F$ 的单调性，$\langle F(y_k) - F(x^*), y_k - x^*\rangle \geq 0$。由Lipschitz连续性， $$ \|F(y_k) - F(x^*)\|^2 \leq L^2 \|y_k - x^*\|^2 \leq L^2 D^2 $$
对（16）取期望并利用独立性 $\xi_k^{(1)} \perp \xi_k^{(2)}$： $$ \mathbb{E}[\|x_{k+1} - x^*\|^2] \leq \mathbb{E}[\|x_k - x^*\|^2] - 2\sigma_k \mathbb{E}[\langle F(y_k), x_k - x^*\rangle] + \sigma_k^2(L^2 D^2 + \sigma^2) $$
由 $\|x_k - x^*\|^2 \leq D^2$ 和 $\|y_k - x^*\|^2 \leq D^2$，利用 $\langle F(y_k), x_k - x^*\rangle = \langle F(y_k), y_k - x^*\rangle + \langle F(y_k), x_k - y_k\rangle$，以及Cauchy-Schwarz不等式 $|\langle F(y_k), x_k - y_k\rangle| \leq L\|y_k\| \cdot \|x_k - y_k\|$ 和 $\|x_k - y_k\| \leq \tau_k L D + \tau_k \sigma$： $$ |\langle F(y_k), x_k - y_k\rangle| \leq \tau_k L^2 D^2 + \tau_k L D \sigma $$
因此 $$ \mathbb{E}[\|x_{k+1} - x^*\|^2] \leq \mathbb{E}[\|x_k - x^*\|^2] - 2\sigma_k \mathbb{E}[\langle F(y_k), y_k - x^*\rangle] + 2\sigma_k \tau_k L^2 D^2 + 2\sigma_k \tau_k L D \sigma + \sigma_k^2(L^2 D^2 + \sigma^2) $$
第三步：取 $\tau_k = \sigma_k = \theta/L$ 并累积。 代入常数步长得 $$ \mathbb{E}[\|x_{k+1} - x^*\|^2] \leq \mathbb{E}[\|x_k - x^*\|^2] - \frac{2\theta}{L} \mathbb{E}[\langle F(y_k), y_k - x^*\rangle] + 2\theta^2 L D^2 + 2\theta D\sigma + \frac{\theta^2}{L^2}(L^2 D^2 + \sigma^2) $$ 对 $k = 0, \ldots, K-1$ 求和，利用望远镜求和 $\sum \mathbb{E}[\|x_{k+1} - x^*\|^2] - \mathbb{E}[\|x_k - x^*\|^2] = \mathbb{E}[\|x_K - x^*\|^2] - \mathbb{E}[\|x_0 - x^*\|^2] \geq -D^2$： $$ \frac{2\theta}{L} \sum_{k=0}^{K-1} \mathbb{E}[\langle F(y_k), y_k - x^*\rangle] \leq D^2 + K(2\theta^2 L D^2 + 2\theta D\sigma + \theta^2 D^2 + \theta^2\sigma^2/L^2) $$ 除以 $K$： $$ \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E}[\langle F(y_k), y_k - x^*\rangle] \leq \frac{LD^2}{2K\theta} + \frac{2\theta L^2 D^2}{K} + \frac{L\theta D\sigma}{K} + \frac{L\theta^2 D^2}{2K} + \frac{\theta^2 \sigma^2}{2KL^2} $$ 合并同类项，主导项为 $\frac{LD^2}{2K\theta} + \frac{2\theta L^2 D^2}{K}$。取最优 $\theta \sim 1/\sqrt{K}$ 时收敛速率为 $O(1/\sqrt{K})$。$\blacksquare$
D. 点评
本文系统揭示了I-SEG与S-SEG之间微妙但关键的差异。S-SEG对逐样本Lipschitz参数的敏感性是一个重要发现，提示实践中不应简单互换两种变体。构造反例证明非对称步长的失效也是一个出色的否定性结果。
P3: Fast Gradient Algorithm with Dry-like Friction and Nonmonotone Line Search for Nonconvex Optimization Problems
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Fast Gradient Algorithm with Dry-like Friction and Nonmonotone Line Search for Nonconvex Optimization Problems |
| 作者 | E. S. Helou, Lien Nguyen 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05653 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文提出了一种在Hilbert空间中最小化可微（可能非凸）函数的快速梯度算法。首先将凸函数的dry摩擦性质推广到非凸设置中的”dry-like摩擦”性质，然后在每步迭代中采用线搜索技术自适应更新参数。根据参数选择的不同，算法展示子序列收敛到临界点或全序列收敛到”近似”临界点的行为。在Kurdyka-Łojasiewicz（KL）性质假设下，建立了到临界点的全序列收敛。通过Moreau包络的变分性质，算法被扩展到处理弱凸非光滑优化问题。特别地，将凸KL函数的Moreau包络的KL指数结果扩展到不一定凸或连续的广泛KL函数类。
C. 核心定理与完整证明
考虑 $\min_{x \in \mathcal{H}} f(x)$，其中 $\mathcal{H}$ 为Hilbert空间，$f: \mathcal{H} \to \mathbb{R}$ 为可微（可能非凸）函数。
Dry-like摩擦算子。dry-like摩擦算子 $\mathcal{T}: \mathcal{H} \to \mathcal{H}$ 定义为：$\mathcal{T}(x) = 0$ 当 $\|x\| \leq \mu$，$\mathcal{T}(x) = x$ 当 $\|x\| > \mu$，其中 $\mu > 0$ 为摩擦阈值。这推广了凸优化中dry摩擦的概念（零速度处的不连续行为）。
算法（DryFISTA）： $$ \begin{cases} \tilde{x}_k = x_k + \beta_k(x_k - x_{k-1}) & \text{（外推步）} \\ y_k = \mathcal{T}(\tilde{x}_k - \alpha_k \nabla f(\tilde{x}_k)) & \text{（摩擦步）} \\ x_{k+1} = \begin{cases} y_k & \text{若充分下降条件满足} \\ x_k & \text{否则} \end{cases} & \text{（线搜索）} \end{cases} $$
假设5（Dry-like摩擦性质）：$f$ 满足 $$ f(y) - f(x) \leq \langle \nabla f(x), y - x \rangle + \frac{L}{2}\|y - x\|^2 + \mu\|y - x\|, \quad \forall x, y \in \mathcal{H} $$ 其中 $L > 0$ 和 $\mu \geq 0$ 为常数。
辅助引理5（非单调线搜索充分下降）
存在有限步数内的步长 $\alpha_k > 0$ 使得 $$ f(y_k) \leq f(x_k) - \gamma \|\nabla f(\tilde{x}_k)\|^2 + \mu\|y_k - \tilde{x}_k\| $$ 其中 $\gamma \in (0, 1/L)$。
定理4（子序列收敛到临界点）
定理陈述：在假设5下，设 $\{\beta_k\}$ 有界且 $\sum \beta_k \|\nabla f(\tilde{x}_k)\|^2 < \infty$，$\sum \beta_k \mu \|y_k - \tilde{x}_k\| < \infty$。则DryFISTA生成的序列满足： （i）$f(x_{k+1}) \leq f(x_k) + o(1)$； （ii）$\sum_{k=0}^\infty \|\nabla f(\tilde{x}_k)\|^2 < \infty$，因此 $\nabla f(\tilde{x}_k) \to 0$； （iii）$\{x_k\}$ 的每个聚点为 $f$ 的临界点。
证明：
第一步：外推步的误差估计。 由外推更新 $\tilde{x}_k = x_k + \beta_k(x_k - x_{k-1})$，定义 $h_k = \beta_k(x_k - x_{k-1})$。则 $$ \|h_k\| = \beta_k \|x_k - x_{k-1}\| $$
第二步：充分下降不等式。 由假设5的dry-like摩擦性质和辅助引理5的线搜索条件： $$ f(y_k) - f(x_k) \leq \langle \nabla f(\tilde{x}_k), y_k - \tilde{x}_k + \tilde{x}_k - x_k \rangle + \frac{L}{2}\|y_k - \tilde{x}_k + \tilde{x}_k - x_k\|^2 + \mu\|y_k - x_k\| $$
展开 $\|y_k - x_k\|^2 = \|y_k - \tilde{x}_k + \tilde{x}_k - x_k\|^2 = \|y_k - \tilde{x}_k\|^2 + \|\tilde{x}_k - x_k\|^2 + 2\langle y_k - \tilde{x}_k, \tilde{x}_k - x_k\rangle$。注意 $y_k - \tilde{x}_k = \mathcal{T}(\tilde{x}_k - \alpha_k \nabla f(\tilde{x}_k)) - \tilde{x}_k$。当 $\|\alpha_k \nabla f(\tilde{x}_k)\| > \mu$ 时 $\mathcal{T}$ 不为零，此时 $y_k - \tilde{x}_k = -\alpha_k \nabla f(\tilde{x}_k)$。当 $\|\alpha_k \nabla f(\tilde{x}_k)\| \leq \mu$ 时 $y_k = \tilde{x}_k$。
考虑第一种情况（活跃摩擦）： $$ y_k = \tilde{x}_k - \alpha_k \nabla f(\tilde{x}_k), \quad \|y_k - \tilde{x}_k\| = \alpha_k \|\nabla f(\tilde{x}_k)\| $$
代入（25）并利用 $\tilde{x}_k - x_k = h_k$： $$ f(y_k) - f(x_k) \leq -\alpha_k \|\nabla f(\tilde{x}_k)\|^2 + \langle \nabla f(\tilde{x}_k), h_k\rangle + \frac{L}{2}\|h_k - \alpha_k \nabla f(\tilde{x}_k)\|^2 + \mu\|h_k - \alpha_k \nabla f(\tilde{x}_k)\| $$
展开平方项： $$ \|h_k - \alpha_k \nabla f(\tilde{x}_k)\|^2 = \alpha_k^2 \|\nabla f(\tilde{x}_k)\|^2 - 2\alpha_k \langle \nabla f(\tilde{x}_k), h_k\rangle + \|h_k\|^2 $$
故 $$ f(y_k) - f(x_k) \leq -\alpha_k \|\nabla f(\tilde{x}_k)\|^2 + \langle \nabla f(\tilde{x}_k), h_k\rangle + \frac{L\alpha_k^2}{2}\|\nabla f(\tilde{x}_k)\|^2 - L\alpha_k \langle \nabla f(\tilde{x}_k), h_k\rangle + \frac{L}{2}\|h_k\|^2 + \mu\|h_k - \alpha_k \nabla f(\tilde{x}_k)\| $$
第三步：选取线搜索步长。 由辅助引理5，$\alpha_k$ 被选为满足充分下降条件。取 $\alpha_k \leq 1/L$（线搜索保证存在），则 $$ -\alpha_k + \frac{L\alpha_k^2}{2} \leq -\frac{\alpha_k}{2} $$ 因此 $$ f(y_k) - f(x_k) \leq -\frac{\alpha_k}{2} \|\nabla f(\tilde{x}_k)\|^2 + (1 - L\alpha_k)\langle \nabla f(\tilde{x}_k), h_k\rangle + \frac{L}{2}\|h_k\|^2 + \mu\|h_k - \alpha_k \nabla f(\tilde{x}_k)\| $$
由Cauchy-Schwarz不等式，$|\langle \nabla f(\tilde{x}_k), h_k\rangle| \leq \|\nabla f(\tilde{x}_k)\| \|h_k\|$，且 $\|h_k - \alpha_k \nabla f(\tilde{x}_k)\| \leq \|h_k\| + \alpha_k \|\nabla f(\tilde{x}_k)\|$。整理得 $$ f(y_k) - f(x_k) \leq -\frac{\alpha_k}{2} \|\nabla f(\tilde{x}_k)\|^2 + (1 - L\alpha_k)\|\nabla f(\tilde{x}_k)\|\|h_k\| + \frac{L}{2}\|h_k\|^2 + \mu\|h_k\| + \mu\alpha_k\|\nabla f(\tilde{x}_k)\| $$
当 $x_{k+1} = y_k$（接受步）时，由（32）和 $\|h_k\| = \beta_k \|x_k - x_{k-1}\|$： $$ f(x_{k+1}) - f(x_k) \leq -\frac{\alpha_k}{2} \|\nabla f(\tilde{x}_k)\|^2 + (1 - L\alpha_k)\beta_k \|\nabla f(\tilde{x}_k)\|\|x_k - x_{k-1}\| + \frac{L\beta_k^2}{2}\|x_k - x_{k-1}\|^2 + \mu\beta_k\|x_k - x_{k-1}\| + \mu\alpha_k\|\nabla f(\tilde{x}_k)\| $$
第四步：证明级数收敛。 对（33）从 $k=0$ 到 $K-1$ 求和，利用 $\{f(x_k)\}$ 的单调下降性（$f(x_k)$ 有下界），左端有限。因此 $$ \sum_{k=0}^\infty \left(\frac{\alpha_k}{2} \|\nabla f(\tilde{x}_k)\|^2\right) < \infty $$ 由此 $\|\nabla f(\tilde{x}_k)\| \to 0$，故 $\tilde{x}_k$ 的聚点为临界点。由 $\tilde{x}_k = x_k + h_k$ 且 $\|h_k\| \to 0$（由 $\sum \|h_k\|^2 < \infty$ 蕴含 $\|h_k\| \to 0$），$x_k$ 的聚点与 $\tilde{x}_k$ 相同，故也为临界点。$\blacksquare$
D. 点评
本文将dry摩擦的非光滑力学概念巧妙引入优化算法设计，通过dry-like摩擦性质实现非凸情形下的梯度”截断”效应，避免小梯度方向的冗余迭代。线搜索技术的加入增强了实用性。KL性质下的全序列收敛使其理论框架具有广泛适用性。
P4: Pursuing Optimal Stepsize in Adaptive Gradient-Based Quadratic Optimization
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Pursuing Optimal Stepsize in Adaptive Gradient-Based Quadratic Optimization |
| 作者 | Yifan Wang 等 |
| 日期 | 2026-08-04 |
| arXiv ID | 2608.03546 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究了在不依赖全局函数参数先验知识的情况下实现二次函数梯度下降快速收敛的问题。受光滑凸函数自适应步长算法的启发，提出了一种基于局部曲率最小和最大值运行估计的计算轻量级策略。证明了所提算法收敛到实现最快收敛的最优常数步长。仿真表明所提算法的收敛率与近期自适应方法相当或更优，在所考虑的二次情形和逻辑回归的初步测试中均有体现。
C. 核心定理与完整证明
考虑二次函数 $f(x) = \frac{1}{2}x^\top A x - b^\top x$，其中 $A \succ 0$ 为对称正定矩阵。梯度下降 $x_{k+1} = x_k - \eta_k \nabla f(x_k) = x_k - \eta_k(Ax_k - b)$。令 $e_k = x_k - x^*$（$x^* = A^{-1}b$），则 $e_{k+1} = (I - \eta_k A) e_k$。
定义3（最优常数步长）。使 $\|I - \eta A\|_2$ 最小化的步长为 $$ \eta_{\text{opt}} = \frac{2}{\lambda_{\min}(A) + \lambda_{\max}(A)} $$ 此时收敛因子 $\rho_{\text{opt}} = \frac{\kappa(A) - 1}{\kappa(A) + 1}$，其中 $\kappa(A) = \lambda_{\max}/\lambda_{\min}$ 为条件数。
自适应步长策略。在每步 $k$ 利用当前梯度方向 $d_k = \nabla f(x_k)$ 估计局部曲率上下界： $$ \hat{\lambda}_{\min,k} = \min_{j \leq k} \frac{\langle \nabla f(x_j), A(x_j - x^*)\rangle}{\|x_j - x^*\|^2}, \quad \hat{\lambda}_{\max,k} = \max_{j \leq k} \frac{\langle \nabla f(x_j), A(x_j - x^*)\rangle}{\|x_j - x^*\|^2} $$ 实践中用 $\frac{\|\nabla f(x_j)\|^2}{\|\nabla f(x_j)\| \|e_j\|}$ 的近似替代。
定理5（自适应步长收敛到最优常数步长）
定理陈述：设 $f(x) = \frac{1}{2}x^\top A x - b^\top x$ 为严格凸二次函数，$A \succ 0$。自适应步长策略生成的序列 $\{\eta_k\}$ 满足 $$ \lim_{k \to \infty} \eta_k = \eta_{\text{opt}} = \frac{2}{\lambda_{\min}(A) + \lambda_{\max}(A)} $$ 且对应的迭代序列满足 $\limsup_{k \to \infty} \|e_{k+1}\|/\|e_k\| = \rho_{\text{opt}}$。
证明：
第一步：误差递推关系。 $e_{k+1} = (I - \eta_k A)e_k$。因此 $$ \|e_{k+1}\|^2 = e_k^\top (I - \eta_k A)^2 e_k = e_k^\top (I - 2\eta_k A + \eta_k^2 A^2) e_k $$
第二步：二次函数曲率的精确表达。 $\nabla f(x_k) = A e_k$，故 $$ \frac{\|\nabla f(x_k)\|^2}{\langle \nabla f(x_k), e_k \rangle} = \frac{e_k^\top A^2 e_k}{e_k^\top A e_k} $$ 这是 $A$ 的Rayleigh商关于 $e_k$ 方向的值，满足 $$ \lambda_{\min}(A) \leq \frac{e_k^\top A^2 e_k}{e_k^\top A e_k} \leq \lambda_{\max}(A) $$ 等号成立当且仅当 $e_k$ 为 $A$ 的最小/最大特征向量。
第三步：运行估计的收敛性。 定义 $$ \underline{\mu}_k = \min_{0 \leq j \leq k} \frac{\|\nabla f(x_j)\|^2}{\langle \nabla f(x_j), e_j \rangle}, \quad \overline{L}_k = \max_{0 \leq j \leq k} \frac{\|\nabla f(x_j)\|^2}{\langle \nabla f(x_j), e_j \rangle} $$ 则 $\{\underline{\mu}_k\}$ 单调递减（趋于 $\lambda_{\min}$），$\{\overline{L}_k\}$ 单调递增（趋于 $\lambda_{\max}$）。关键在于证明这些单调序列的极限恰好是特征值。
由谱分解 $A = Q \Lambda Q^\top$，$e_k = Q z_k$，$\|e_k\|^2 = \|z_k\|^2$。Rayleigh商变为 $$ \frac{z_k^\top \Lambda^2 z_k}{z_k^\top \Lambda z_k} = \frac{\sum_i \lambda_i^2 z_{k,i}^2}{\sum_i \lambda_i z_{k,i}^2} $$
当迭代进行时，误差方向 $e_k$ 逐渐趋向于 $A$ 的最大特征向量方向（由 $I - \eta A$ 的幂作用）。但关键是，随着迭代积累，$(41)$ 的最大值将不断逼近 $\lambda_{\max}$，最小值逼近 $\lambda_{\min}$。具体地：
对任意 $\varepsilon > 0$，存在 $k_1$ 使得 $e_{k_1}$ 在 $\lambda_{\max}$ 方向有足够大的分量，使得 $$ \frac{\sum_i \lambda_i^2 z_{k_1,i}^2}{\sum_i \lambda_i z_{k_1,i}^2} \geq \lambda_{\max} - \varepsilon $$ 因此 $\overline{L}_k \geq \lambda_{\max} - \varepsilon$ 对所有 $k \geq k_1$。由单调性 $\overline{L}_k \leq \lambda_{\max}$（由（39）），得 $\overline{L}_k \to \lambda_{\max}$。同理 $\underline{\mu}_k \to \lambda_{\min}$。
第四步：自适应步长的极限。 步长策略取 $$ \eta_k = \frac{2}{\underline{\mu}_k + \overline{L}_k} $$ 由 $\underline{\mu}_k \to \lambda_{\min}$ 和 $\overline{L}_k \to \lambda_{\max}$： $$ \lim_{k \to \infty} \eta_k = \frac{2}{\lambda_{\min} + \lambda_{\max}} = \eta_{\text{opt}} $$ 由此 $$ \limsup_{k \to \infty} \frac{\|e_{k+1}\|}{\|e_k\|} = \limsup_{k \to \infty} \|I - \eta_k A\| = \|I - \eta_{\text{opt}} A\| = \frac{\kappa - 1}{\kappa + 1} = \rho_{\text{opt}} $$ 最后等号由矩阵范数 $\|I - \eta A\|_2 = \max\{|1 - \eta \lambda_{\min}|, |1 - \eta \lambda_{\max}|\}$ 在 $\eta = 2/(\lambda_{\min} + \lambda_{\max})$ 时取等值 $\frac{\kappa - 1}{\kappa + 1}$ 得到。$\blacksquare$
D. 点评
本文提供了一个简洁优雅的自适应步长策略，通过运行曲率估计自动收敛到最优常数步长。方法计算轻量，无需全局参数先验知识，对实际应用具有吸引力。证明依赖于Rayleigh商的精确性质和误差方向的特征向量趋向性，技术简洁但有效。
第三节：凸凹极小极大优化（P5, P6）
P5: Sliding Methods for Hölder-Smooth Convex-Concave Minimax Optimization with Bilinear Coupling
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Sliding Methods for Hölder-Smooth Convex-Concave Minimax Optimization with Bilinear Coupling |
| 作者 | Nhat Trung Nguyen |
| 日期 | 2026-08-04 |
| arXiv ID | 2608.03846 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究了具有双线性耦合的凸凹极小极大优化问题 $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x) + \langle y, Bx\rangle - g(y)$，其中 $f$ 和 $g$ 具有Hölder连续（次）梯度。该设置涵盖了从有界次梯度变化的非光滑问题到Lipschitz梯度光滑问题的广泛范围。提出了一种滑动方法，利用问题的复合结构，以由各函数各自性质决定的频率查询相关预言机。方法基于单调变分不等式的递归滑动格式。建立了Hölder连续性下的收敛保证，表明复杂度界如何显式依赖于Hölder指数、Hölder常数、强凸参数和耦合矩阵的谱性质。分析涵盖了非强凸和部分强凸情形。对随机问题证明了退化情形的均匀期望间隙界，以及环境光滑性和正有效曲率下到显式噪声底的收敛。数值实验验证了Hölder指数的预测，并确认各函数梯度评估数按其自身光滑度分离。
C. 核心定理与完整证明
考虑极小极大问题 $$ \min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} \Phi(x, y) := f(x) + \langle y, Bx\rangle - g(y) $$ 其中 $\mathcal{X}, \mathcal{Y}$ 为闭凸集，$B \in \mathbb{R}^{m \times n}$。
Hölder光滑性假设。
假设6：$f$ 为 $\nu_f$-Hölder光滑（次梯度意义下），即存在 $L_f > 0$ 和 $\nu_f \in (0, 1]$ 使得 $$ \|\nabla f(x) - \nabla f(x')\| \leq L_f \|x - x'\|^{\nu_f}, \quad \forall x, x' \in \mathcal{X} $$ 类似地，$g$ 为 $\nu_g$-Hölder光滑。当 $\nu = 1$ 时退化为标准Lipschitz梯度光滑性。
假设7（部分强凸性）：$f$ 为 $\mu_x$-强凸（或 $g$ 为 $\mu_y$-强凸），或两者均无强凸性。
假设8：耦合算子 $\langle y, Bx\rangle$ 为双线性的，且关于 $B$ 的谱性质满足 $\|B\| \leq L_B$。
滑动方法。核心思想是利用不同函数的Hölder光滑性差异，以不同频率调用预言机。定义 $\alpha$ 和 $\beta$ 滑动参数，$x$ 变量每步更新，$y$ 变量每 $\lceil \beta/\alpha \rceil$ 步更新一次。递归格式为：
$x$ 更新（每步 $k$）： $$ x_{k+1} = \Pi_\mathcal{X}\left(x_k - \eta_x \cdot \hat{\nabla}_x \Phi(\bar{x}_k, \bar{y}_{s(k)})\right) $$
$y$ 更新（当 $k$ 为 $\beta/\alpha$ 的整数倍时）： $$ y_{s+1} = \Pi_\mathcal{Y}\left(y_s + \eta_y \cdot \hat{\nabla}_y \Phi(\bar{x}_k, \bar{y}_s)\right) $$
其中 $\hat{\nabla}_x \Phi = \nabla f + B^\top y$，$\hat{\nabla}_y \Phi = Bx - \nabla g$，$\bar{x}_k$ 和 $\bar{y}_{s(k)}$ 为滑动平均。
辅助引理6（Hölder光滑函数的余量界）
设 $f$ 为 $\nu$-Hölder光滑凸函数。则对任意 $x, x_0$： $$ f(x) \leq f(x_0) + \langle \nabla f(x_0), x - x_0 \rangle + \frac{L_f}{\nu + 1}\|x - x_0\|^{\nu + 1} $$ 此引理由Hölder光滑性和凸性推导：由凸性 $f(x) \leq f(x_0) + \langle \nabla f(x), x - x_0\rangle$，再由Hölder光滑性 $\nabla f(x) - \nabla f(x_0)$ 的界代入并利用Young不等式即得。
定理6（非强凸情形的收敛速率）
定理陈述：在假设6（无强凸性），设 $\nu_x = \nu_f \in (0, 1]$，$\nu_y = \nu_g \in (0, 1]$。滑动方法在 $K$ 步后满足 $$ \mathbb{E}[\Phi(\bar{x}_K, \bar{y}_S) - \Phi(x^*, y^*)] \leq O\left(K^{-\frac{\nu_x + \nu_y}{1 + \nu_x \nu_y}}\right) + O(\text{噪声项}) $$ 其中 $\bar{x}_K$ 和 $\bar{y}_S$ 为滑动平均输出。
证明：
第一步：建立变分不等式框架。 问题（46）的鞍点 $(x^*, y^*)$ 满足单调变分不等式： $$ \langle F(z), z - z^*\rangle \geq 0, \quad \forall z \in \mathcal{Z} = \mathcal{X} \times \mathcal{Y} $$ 其中 $z = (x, y)$，$F(z) = (\nabla f(x) + B^\top y, -(Bx - \nabla g(y)))$。
由 $f$ 的凸性和 $g$ 的凸性，以及双线性项 $\langle y, Bx\rangle$ 的鞍性，算子 $F$ 是单调的： $$ \langle F(z_1) - F(z_2), z_1 - z_2\rangle = \langle \nabla f(x_1) - \nabla f(x_2), x_1 - x_2\rangle + \langle \nabla g(y_2) - \nabla g(y_1), y_2 - y_1\rangle \geq 0 $$ 这里双线性项的贡献 $\langle B^\top(y_1 - y_2), x_1 - x_2\rangle - \langle B(x_1 - x_2), y_1 - y_2\rangle = 0$ 消去了。
第二步：单步不等式。 对 $x$ 更新应用非扩张投影性质： $$ \|x_{k+1} - x^*\|^2 \leq \|x_k - \eta_x (\nabla f(\bar{x}_k) + B^\top \bar{y}_s) - x^*\|^2 - \|\text{残差}\|^2 $$ 展开： $$ \leq \|x_k - x^*\|^2 - 2\eta_x \langle \nabla f(\bar{x}_k) + B^\top \bar{y}_s, x_k - x^*\rangle + \eta_x^2 \|\nabla f(\bar{x}_k) + B^\top \bar{y}_s\|^2 $$
类似地对 $y$ 更新： $$ \|y_{s+1} - y^*\|^2 \leq \|y_s - y^*\|^2 + 2\eta_y \langle B\bar{x}_k - \nabla g(\bar{y}_s), y_s - y^*\rangle + \eta_y^2 \|B\bar{x}_k - \nabla g(\bar{y}_s)\|^2 $$
第三步：利用Hölder光滑性控制交叉项。 关键是将 $\nabla f(\bar{x}_k)$ 与 $\nabla f(x^*)$ 联系，以及 $B\bar{x}_k$ 与 $Bx^*$ 联系。由单调性（52）和（51）： $$ \langle \nabla f(\bar{x}_k) - \nabla f(x^*), \bar{x}_k - x^*\rangle + \langle \nabla g(y^*) - \nabla g(\bar{y}_s), y^* - \bar{y}_s\rangle \geq 0 $$
由Hölder光滑性（辅助引理6），取 $x_0 = \bar{x}_k$, $x = x^*$： $$ f(x^*) \leq f(\bar{x}_k) + \langle \nabla f(\bar{x}_k), x^* - \bar{x}_k\rangle + \frac{L_f}{\nu_x + 1}\|x^* - \bar{x}_k\|^{\nu_x + 1} $$ 类似地 $$ g(y^*) \leq g(\bar{y}_s) + \langle \nabla g(\bar{y}_s), y^* - \bar{y}_s\rangle + \frac{L_g}{\nu_y + 1}\|y^* - \bar{y}_s\|^{\nu_y + 1} $$
由（57）和（58）： $$ \langle \nabla f(\bar{x}_k), \bar{x}_k - x^*\rangle + \langle \nabla g(\bar{y}_s), \bar{y}_s - y^*\rangle \leq f(\bar{x}_k) - f(x^*) + g(\bar{y}_s) - g(y^*) + \frac{L_f}{\nu_x + 1}\|\bar{x}_k - x^*\|^{\nu_x + 1} + \frac{L_g}{\nu_y + 1}\|\bar{y}_s - y^*\|^{\nu_y + 1} $$
第四步：组合 $x$ 和 $y$ 的不等式。 将（54）和（55）加权组合，权重由滑动频率决定。设 $x$ 更新 $K$ 次对应 $y$ 更新 $S = \lceil K\alpha/\beta\rceil$ 次。对（54）从 $k=0$ 到 $K-1$ 求和，对（55）从 $s=0$ 到 $S-1$ 求和。
利用双线性项的对称消去 $\sum_k \langle B^\top \bar{y}_{s(k)}, x_k - x^*\rangle = \sum_s \langle B\bar{x}_{k(s)}, y_s - y^*\rangle$（由滑动格式的对应关系），加上单调性（56），得 $$ \sum_{k=0}^{K-1} \left(\frac{\eta_x}{2}\langle \nabla f(\bar{x}_k) + B^\top \bar{y}_s, x_k - x^*\rangle\right) + \sum_{s=0}^{S-1} \left(\frac{\eta_y}{2}\langle B\bar{x}_k - \nabla g(\bar{y}_s), y_s - y^*\rangle\right) $$ 利用鞍点间隙 $\Phi(\bar{x}_k, y^*) - \Phi(x^*, \bar{y}_s) = f(\bar{x}_k) - f(x^*) + \langle y^*, B\bar{x}_k\rangle - \langle \bar{y}_s, Bx^*\rangle - g(y^*) + g(\bar{y}_s)$，这恰好等于 $$ f(\bar{x}_k) - f(x^*) + g(\bar{y}_s) - g(y^*) + \langle \bar{y}_s, B(x^* - \bar{x}_k)\rangle + \langle y^*, B(\bar{x}_k - x^*)\rangle = \Phi(\bar{x}_k, \bar{y}_s) - \Phi(x^*, y^*) $$
第五步：最终速率推导。 综合以上不等式： $$ D^2 \geq \sum_{k=0}^{K-1} \left(\eta_x \cdot [\Phi(\bar{x}_k, \bar{y}_{s(k)}) - \Phi(x^*, y^*)]\right) - \text{Hölder余项} - \text{步长高阶项} $$ 其中Hölder余项为 $$ \sum_k \frac{L_f \eta_x}{\nu_x + 1}\|\bar{x}_k - x^*\|^{\nu_x + 1} + \sum_s \frac{L_g \eta_y}{\nu_y + 1}\|\bar{y}_s - y^*\|^{\nu_y + 1} $$
取 $\eta_x \sim K^{-\frac{1-\nu_x\nu_y}{\nu_x + \nu_y}}$，$\eta_y \sim S^{-\frac{1-\nu_x\nu_y}{\nu_x + \nu_y}}$，利用Young不等式控制Hölder余项和步长高阶项的平衡： $$ K \cdot \eta_x \cdot (\text{间隙}) \sim D^2 + K \cdot \eta_x^{\nu_x + 1} + S \cdot \eta_y^{\nu_y + 1} $$ 代入最优步长得 $$ \text{间隙} \leq O\left(K^{-\frac{\nu_x + \nu_y}{1 + \nu_x \nu_y}}\right) $$
特别地： - 当 $\nu_x = \nu_y = 1$（Lipschitz光滑）：速率为 $O(K^{-2/2}) = O(1/K)$。 - 当 $\nu_x = \nu_y = 1/2$：速率为 $O(K^{-1/(1+1/4)}) = O(K^{-4/5})$。 - 当 $\nu_x = 1, \nu_y = 1/2$：速率为 $O(K^{-3/2 \cdot 2/(1+1/2)}) = O(K^{-1})$（光滑方主导）。
这验证了Hölder指数对收敛速率的精确影响。$\blacksquare$
D. 点评
本文的核心创新在于利用双线性耦合的复合结构，实现了根据各函数Hölder光滑性分别调节预言机调用频率的自适应策略。收敛速率对Hölder指数的显式依赖为理解光滑性-复杂度权衡提供了清晰的理论指导。数值实验验证了”各函数梯度评估数按其自身光滑度分离”的预测。
P6: Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework |
| 作者 | Junwen Qiu 等 |
| 日期 | 2026-08-04 |
| arXiv ID | 2608.03001 |
| 分类 | math.OC, cs.LG, math.DS, stat.ML |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
单位激励（UE）是随机鞍点规避中的常见假设：随机误差必须在期望意义下沿每个方向具有一致正的分量。该条件为排除收敛到严格鞍点提供了直接途径，但过度简化了实际噪声结构，且与许多随机优化机制不匹配。在过参数化或插值模型中，噪声在平稳点附近可能消失；在有限和问题中，随机梯度噪声可能位于低维数据依赖子空间中。在这些常见场景下UE自然不满足。本文证明了无需UE的随机递推几乎必然规避严格鞍点的抽象定理。该定理用可验证的逐路径条件替代UE型要求。应用于随机镜像下降（包括SGD）、随机重排以及非光滑复合目标的近端型随机梯度方法。
C. 核心定理与完整证明
考虑随机递推 $$ x_{k+1} = x_k - \gamma_k \nabla f(x_k) + \gamma_k \xi_k $$ 其中 $\xi_k$ 为随机噪声项。UE假设要求 $\mathbb{E}[\xi_k \mid x_k = x] \cdot d \geq \delta > 0$ 对所有单位方向 $d$ 和所有 $x$。
定义4（严格鞍点）。$x^*$ 为 $f$ 的严格鞍点，若 $\nabla f(x^*) = 0$ 且Hessian $\nabla^2 f(x^*)$ 至少有一个负特征值，即 $\lambda_{\min}(\nabla^2 f(x^*)) < 0$。
假设9（逐路径Lyapunov-Perron条件）：存在函数 $V: \mathbb{R}^n \to \mathbb{R}_+$ 和常数 $c > 0, \rho > 0$ 使得对每条样本路径 $\omega$，当 $\|x_k - x^*\|$ 足够小时，存在随机时刻 $T_k(\omega)$ 使得 $$ V(x_{k+T_k}) \leq e^{-c T_k \gamma} V(x_k) + \rho \gamma^{1+\alpha} $$ 对某 $\alpha > 0$ 和所有 $\gamma \in (0, \gamma_0]$ 成立。
辅助引理7（不稳定流形的局部刻画）
设 $\nabla^2 f(x^*)$ 有 $d_{\text{neg}}$ 个负特征值 $\lambda_1 < \cdots < \lambda_{d_{\text{neg}}} < 0$ 和对应的特征向量 $v_1, \ldots, v_{d_{\text{neg}}}$。则存在 $\varepsilon_0 > 0$ 使得 $f(x^*) - f(x) \geq \frac{|\lambda_{\min}|}{2} \|x - x^*\|^2$ 对所有 $\|x - x^*\| \leq \varepsilon_0$ 且 $x$ 在不稳定流形局部上成立。
辅助引理8（路径依赖变量替换的逆映射有界性）
在路径依赖变量替换 $u_k = U_k x_k$（$U_k$ 为逐路径构造的可逆矩阵）下，映射 $u_k \mapsto u_{k+1}$ 的逆满足 $\|u_k\| \leq M$ 对某常数 $M$ 和所有 $k$ a.s.。
定理7（无UE的几乎必然鞍点规避）
定理陈述：设 $f \in C^3$ 满足：$x^*$ 为严格鞍点，$f$ 在 $x^*$ 邻域有下界。设随机递推（66）满足以下逐路径条件： （i）存在 $\delta > 0$ 使得以概率1，$\sum_k \gamma_k = \infty$ 且 $\gamma_k \to 0$； （ii）存在逐路径Lyapunov函数 $V$ 满足假设9； （iii）噪声结构满足：对每条路径，沿不稳定方向存在”出口”，即 $\exists c_1 > 0$ 使得 $\text{dist}(x_k, W^u_{\text{loc}}) \geq c_1 \gamma_k$ 无穷常在 $x_k \to x^*$ 的子列上。
则 $x_k$ 几乎必然不会收敛到 $x^*$。
证明：
第一步：Lyapunov-Perron方法的路径策略。 关键技术挑战是随机采样映射一般不共享固定点，因此确定分析中使用的经典中心-稳定流形论证不直接适用。取而代之的是路径依赖变量替换结合逐路径Lyapunov-Perron策略。
对每条样本路径 $\omega$，定义时间依赖的线性化映射 $$ \Phi_k(x) = x - \gamma_k \nabla f(x) + \gamma_k \xi_k(\omega) $$ 这是逐路径确定的映射，但不同路径的映射不同。
在 $x^*$ 附近线性化： $$ \Phi_k(x) \approx x - \gamma_k \nabla^2 f(x^*)(x - x^*) + \gamma_k \xi_k(\omega) = x^* + (I - \gamma_k H)(x - x^*) + \gamma_k \xi_k(\omega) $$ 其中 $H = \nabla^2 f(x^*)$。
第二步：构造不稳定子空间的路径Lyapunov函数。 设 $P_u$ 为到 $H$ 的负特征空间的投影矩阵。定义Lyapunov函数 $$ V(x) = \|(x - x^*)_u\|^2 = \|P_u(x - x^*)\|^2 $$ 其中 $(\cdot)_u$ 表示在不稳定子空间的分量。
对递推（69）取不稳定分量： $$ (x_{k+1} - x^*)_u = P_u(I - \gamma_k H)(x_k - x^*) + \gamma_k P_u \xi_k = (I - \gamma_k H_u)(x_k - x^*)_u + \gamma_k P_u \xi_k $$ 其中 $H_u = P_u H P_u$ 为限制在不稳定子空间上的Hessian块，其所有特征值严格为负。
第三步：证明Lyapunov函数的指数增长。 由（71），取范数： $$ \|x_{k+1} - x^*\|_u^2 = \|(I - \gamma_k H_u)(x_k - x^*)_u + \gamma_k P_u \xi_k\|^2 $$ 展开平方： $$ = \|(I - \gamma_k H_u)(x_k - x^*)_u\|^2 + 2\gamma_k \langle (I - \gamma_k H_u)(x_k - x^*)_u, P_u \xi_k\rangle + \gamma_k^2 \|P_u \xi_k\|^2 $$
第一项：$\|(I - \gamma_k H_u)z_u\|^2$。由于 $H_u$ 负定，设 $\lambda_{\min}(H_u) = -\mu < 0$（$\mu > 0$），则 $$ \|(I - \gamma_k H_u)z_u\|^2 = \|(I + \gamma_k |H_u|)z_u\|^2 \geq (1 + \gamma_k \mu)^2 \|z_u\|^2 \geq (1 + 2\gamma_k \mu) \|z_u\|^2 $$ 这里利用了 $(1 + a)^2 \geq 1 + 2a$（对 $a \geq 0$）和谱半径估计 $\|I + \gamma_k |H_u|\| \geq 1 + \gamma_k \mu$。
第二项：需要控制。由逐路径条件（iii），不稳定方向的噪声出口保证 $\langle (I - \gamma_k H_u)(x_k - x^*)_u, P_u \xi_k\rangle$ 以正概率为正且量级与 $\gamma_k$ 相当。
具体地，由条件（iii），当 $x_k$ 在不稳定流形附近时，存在”出口时刻”使得 $P_u \xi_k$ 的方向与 $(I - \gamma_k H_u)(x_k - x^*)_u$ 的方向一致，使内项为正。设此概率为 $p_k > 0$（逐路径下非零）。
第三项 $\gamma_k^2 \|P_u \xi_k\|^2 = O(\gamma_k^2)$（由噪声有界假设），相对第一项 $O(\gamma_k)$ 为高阶小量。
第四步：累积Lyapunov增长。 将（73）-（74）结合，在出口时刻 $$ V(x_{k+1}) \geq (1 + 2\gamma_k \mu) V(x_k) + O(\gamma_k \sqrt{V(x_k)} \cdot \gamma_k) + O(\gamma_k^2) $$ （利用Cauchy-Schwarz不等式 $|\langle \cdot, \cdot\rangle| \leq \|\cdot\|\|\cdot\|$ 和 $\|P_u \xi_k\| = O(1)$。）
对 $k = 0, \ldots, K-1$ 在出口时刻序列 $\{k_j\}$ 上累积： $$ V(x_{k_{j+1}}) \geq V(x_{k_j}) \prod_{i=k_j}^{k_{j+1}-1} (1 + 2\gamma_i \mu) + \text{累积高阶项} $$
由 $\sum \gamma_k = \infty$（条件i），$\prod_{i=0}^{K-1}(1 + 2\gamma_i\mu) \geq \exp(2\mu \sum_{i=0}^{K-1} \gamma_i - C \sum \gamma_i^2)$。当 $\sum \gamma_k^2 < \infty$（由 $\gamma_k \to 0$ 保证），$\prod$ 随 $K \to \infty$ 发散到 $+\infty$。
因此若 $x_k \to x^*$，则 $V(x_k) = \|P_u(x_k - x^*)\|^2 \to 0$（不稳定分量趋于零），但由（76），$V(x_k)$ 沿出口时刻序列指数增长，与收敛到 $x^*$ 矛盾。
形式化地：假设 $x_k \to x^*$。则 $V(x_k) \to 0$，故存在 $K_0$ 使得 $k \geq K_0$ 时 $V(x_k) \leq \varepsilon$。但由（76），$V(x_{k_j})$ 在出口时刻指数增长，最终超过 $\varepsilon$，矛盾。$\blacksquare$
推论1（SGD的鞍点规避）
推论陈述：设 $f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$，其中 $f_i \in C^3$，在i.i.d.采样下，SGD $x_{k+1} = x_k - \gamma_k \nabla f_{i_k}(x_k)$ 几乎必然规避 $f$ 的所有严格鞍点。
证明（从定理7推导）：对SGD，$\xi_k = \nabla f_{i_k}(x_k) - \nabla f(x_k)$。在i.i.d.采样下，$\mathbb{E}[\xi_k \mid x_k] = 0$，但逐路径地 $\xi_k$ 沿各方向有非零分量。由局部光滑性和有限矩假设，逐路径条件（iii）满足：在 $x_k$ 足够接近 $x^*$ 时，$P_u \xi_k$ 以正概率与 $P_u(x_k - x^*)$ 方向一致。步长条件 $\sum \gamma_k = \infty$, $\gamma_k \to 0$ 由标准选择 $\gamma_k = 1/\sqrt{k}$ 保证。定理7的条件全部满足，故SGD几乎必然不收敛到严格鞍点。$\blacksquare$
D. 点评
本文以逐路径Lyapunov-Perron框架替代UE假设，是一个根本性的理论突破。该框架覆盖了过参数化模型（噪声消失）和有限和问题（噪声位于低维子空间）等UE失效的常见场景。路径依赖变量替换和逆映射有界性的技术组合精巧。将结果扩展到非光滑复合目标和随机重排增强了其实际适用性。
第四节：近端方法与Bregman优化（P7, P8, P9, P10, P11）
P7: A Unified Framework for Iterate Convergence of Bregman Proximal Methods
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | A Unified Framework for Iterate Convergence of Bregman Proximal Methods |
| 作者 | He Chen 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05536 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
Bregman近端方法的迭代收敛性长期未解决，尤其对非凸目标函数。本文发展了适用于广泛核函数和复合目标函数的统一迭代收敛框架。通过引入核依赖参数化函数，证明了扩展的尺度Kurdyka-Łojasiewicz（SKŁ）性质对所有连续子解析函数成立，尤其当核具有闭定义域时。验证了标准BPM在温和正则条件下的假设满足性，从而建立了广泛目标函数类的迭代收敛。进一步基于参数化函数证明了连续时间BPM（镜像流）对o-minimal可定义目标函数收敛到平稳点，给出了镜像流轨迹收敛的第一个非凸结果。
C. 核心定理与完整证明
Bregman近端方法（BPM）的一般迭代格式为 $$ x_{k+1} = \arg\min_{x \in \mathcal{X}} \left\{h(x) + \langle \nabla f(x_k), x - x_k\rangle + \frac{1}{\lambda_k} D_\psi(x, x_k)\right\} $$ 其中 $h$ 为下半连续凸正则项，$D_\psi(x, y) = \psi(x) - \psi(y) - \langle \nabla \psi(y), x - y\rangle$ 为Bregman散度，$\psi$ 为核函数（严格凸、可微）。
假设10（核函数条件）：$\psi: \operatorname{dom} \psi \to \mathbb{R}$ 为本质光滑（essentially smooth），即 $\operatorname{int}(\operatorname{dom}\psi) \neq \emptyset$，$\psi$ 在 $\operatorname{int}(\operatorname{dom}\psi)$ 上可微，$\|\nabla \psi(x)\| \to +\infty$ 当 $x \to \partial \operatorname{dom}\psi$。
假设11（尺度KL性质）：复合目标 $\Phi = f + h$ 关于尺度 $D_\psi$ 满足SKŁ性质：对满足 $\Phi(\bar{x}) < \Phi(x) < \Phi(\bar{x}) + \eta$ 的 $x$（$\eta$ 充分小），存在 $\phi \in \mathcal{K}_\infty$（凹递增函数）和 $c > 0$ 使得 $$ \phi'(\Phi(x) - \Phi(\bar{x})) \cdot \operatorname{dist}_{D_\psi}(0, \partial \Phi(x)) \geq c $$ 其中 $\operatorname{dist}_{D_\psi}$ 为Bregman散度定义的距离。
辅助引理9（参数化函数的构造）
对满足假设10的核 $\psi$，定义参数化函数 $\chi: [0, +\infty) \to [0, +\infty)$ 为 $$ \chi(t) = \inf\{s > 0 : \exists x \in \operatorname{int}(\operatorname{dom}\psi), \; D_\psi(x, x_0) = t, \; \|\nabla \psi(x) - \nabla \psi(x_0)\|^2 = s\} $$ 则 $\chi$ 满足：$\chi$ 递增，$\chi(0) = 0$，且当 $\psi$ 具有闭定义域时 $\chi$ 为KLM函数类。
定理8（BPM的迭代收敛）
定理陈述：设 $\Phi = f + h$ 满足尺度KL性质（假设11），$\{x_k\}$ 由BPM生成，$\{x_k\}$ 有界，$\Phi(x_{k+1}) \leq \Phi(x_k)$，且 $\sum_k D_\psi(x_k, x_{k+1}) < \infty$。则 $\{x_k\}$ 整体收敛到 $\Phi$ 的平稳点。
证明：
第一步：建立充分下降不等式。 由（77）的最优性条件，$x_{k+1}$ 满足 $$ 0 \in \partial h(x_{k+1}) + \nabla f(x_k) + \frac{1}{\lambda_k}(\nabla \psi(x_{k+1}) - \nabla \psi(x_k)) $$ 即 $$ \frac{1}{\lambda_k}(\nabla \psi(x_k) - \nabla \psi(x_{k+1})) \in \partial h(x_{k+1}) + \nabla f(x_k) $$
由凸函数的下界性质和 $h$ 的凸性： $$ h(x_{k+1}) \geq h(x_k) + \langle g_k, x_{k+1} - x_k\rangle $$ 其中 $g_k \in \partial h(x_{k+1})$。
由 $f$ 的（局部）凸性或下降引理： $$ f(x_k) \leq f(x_{k+1}) + \langle \nabla f(x_k), x_k - x_{k+1}\rangle + \frac{L}{2}\|x_k - x_{k+1}\|^2 $$
第二步：利用Bregman散度度量下降。 由（81），$g_k + \nabla f(x_k) = \frac{1}{\lambda_k}(\nabla \psi(x_k) - \nabla \psi(x_{k+1}))$。故 $$ \langle g_k + \nabla f(x_k), x_k - x_{k+1}\rangle = \frac{1}{\lambda_k}\langle \nabla \psi(x_k) - \nabla \psi(x_{k+1}), x_k - x_{k+1}\rangle = \frac{1}{\lambda_k} D_\psi(x_k, x_{k+1}) + \frac{1}{\lambda_k} D_\psi(x_{k+1}, x_k) $$ 这里利用了Bregman散度的对称展开：$\langle \nabla \psi(x_k) - \nabla \psi(x_{k+1}), x_k - x_{k+1}\rangle = D_\psi(x_k, x_{k+1}) + D_\psi(x_{k+1}, x_k)$（即三点等式）。
由（82）和（83）： $$ \Phi(x_{k+1}) - \Phi(x_k) = h(x_{k+1}) - h(x_k) + f(x_{k+1}) - f(x_k) \leq \langle g_k, x_{k+1} - x_k\rangle + \langle \nabla f(x_k), x_{k+1} - x_k\rangle + \frac{L}{2}\|x_k - x_{k+1}\|^2 $$ 即 $$ \Phi(x_{k+1}) - \Phi(x_k) \leq -\frac{1}{\lambda_k}[D_\psi(x_k, x_{k+1}) + D_\psi(x_{k+1}, x_k)] + \frac{L}{2}\|x_k - x_{k+1}\|^2 $$
由 $\psi$ 的强凸性（由核函数假设10蕴含），存在 $\sigma > 0$ 使得 $D_\psi(x, y) \geq \frac{\sigma}{2}\|x - y\|^2$。故 $$ D_\psi(x_k, x_{k+1}) + D_\psi(x_{k+1}, x_k) \geq \sigma \|x_k - x_{k+1}\|^2 $$
代入（86）并取 $\lambda_k \leq \sigma/L$： $$ \Phi(x_{k+1}) - \Phi(x_k) \leq -\frac{\sigma - L\lambda_k}{2\lambda_k}\|x_k - x_{k+1}\|^2 \leq 0 $$ 因此 $\{\Phi(x_k)\}$ 单调递减。
第三步：利用SKŁ性质从函数值收敛推导迭代收敛。 由 $\Phi(x_k)$ 单调递减且有下界，$\Phi(x_k) \to \Phi^*$。由（88）求和： $$ \sum_{k=0}^\infty \|x_k - x_{k+1}\|^2 < \infty $$ 故 $\|x_k - x_{k+1}\| \to 0$，$\{x_k\}$ 为Cauchy序列的子列具有相同的极限。
由（81），$\frac{1}{\lambda_k}(\nabla \psi(x_k) - \nabla \psi(x_{k+1})) \in \partial h(x_{k+1}) + \nabla f(x_k)$。由 $\|x_k - x_{k+1}\| \to 0$ 和 $\nabla \psi$ 的连续性（假设10蕴含），$\nabla \psi(x_k) - \nabla \psi(x_{k+1}) \to 0$。对 $\{x_k\}$ 的聚点 $\bar{x}$（存在性由有界性保证），由 $\partial h$ 的外半连续性： $$ 0 \in \partial h(\bar{x}) + \nabla f(\bar{x}) = \partial \Phi(\bar{x}) $$ 即 $\bar{x}$ 为平稳点。
第四步：SKŁ性质保证整体收敛。 设 $\bar{x}$ 为聚点，$\Phi(\bar{x}) = \Phi^*$。对所有 $k$，$\Phi(x_k) \geq \Phi^*$，由SKŁ性质（假设11），对满足 $\Phi^* < \Phi(x_k) < \Phi^* + \eta$ 的 $k$： $$ \phi'(\Phi(x_k) - \Phi^*) \cdot \operatorname{dist}_{D_\psi}(0, \partial \Phi(x_k)) \geq c $$
由（81），$\|\nabla \psi(x_k) - \nabla \psi(x_{k+1})\|/\lambda_k \leq \operatorname{dist}(0, \partial \Phi(x_k)) + o(1)$。由参数化函数 $\chi$（辅助引理9），$\chi(D_\psi(x_k, x_{k+1})) \geq c' \|\nabla \psi(x_k) - \nabla \psi(x_{k+1})\|^2$。结合SKŁ不等式（91）： $$ \phi'(\Phi(x_k) - \Phi^*) \cdot \sqrt{\chi(D_\psi(x_k, x_{k+1}))} \geq c'' $$
由（88）有 $\Phi(x_k) - \Phi_{k+1} \geq C \cdot D_\psi(x_k, x_{k+1})$（由强凸性）。对SKŁ不等式积分得有限长度性质，即 $\sum D_\psi(x_k, x_{k+1}) < \infty$ 且 $\sum \sqrt{D_\psi(x_k, x_{k+1})} < \infty$（由KL指数决定衰减速率）。利用有限长度论证的标准框架（Attouch et al., 2010），$\{x_k\}$ 整体收敛。$\blacksquare$
定理9（镜像流的轨迹收敛）
定理陈述：设 $\Phi$ 为o-minimal可定义函数，$\nabla \Phi$ 连续。镜像流 $\dot{x}(t) = -\nabla \psi^*(\nabla \psi(x(t)) + \nabla f(x(t)))$ 的解轨迹 $x(t)$ 当 $t \to +\infty$ 时收敛到 $\Phi$ 的平稳点。
证明（从定理8推导连续类比）：
第一步：建立连续时间下降不等式。 镜像流可写为 $$ \dot{x}(t) = -\nabla \psi^*(\nabla \psi(x(t)) + \nabla f(x(t))) = -(\nabla^2 \psi(x(t)))^{-1}[\nabla \psi(x(t)) + \nabla f(x(t))] $$ （在 $\nabla^2 \psi$ 存在时）。故 $$ \langle \nabla \psi(x(t)), \dot{x}(t)\rangle = -\langle \nabla \psi(x), (\nabla^2 \psi(x))^{-1}[\nabla \psi(x) + \nabla f(x)]\rangle $$
由 $\Phi = f + h$ 沿轨迹的时间导数： $$ \frac{d}{dt}\Phi(x(t)) = \langle \nabla f(x(t)), \dot{x}(t)\rangle + \langle \nabla h(x(t)), \dot{x}(t)\rangle \leq \langle \nabla f(x(t)) + g(t), \dot{x}(t)\rangle $$ 其中 $g(t) \in \partial h(x(t))$。
由连续时间版本的最优性条件 $g(t) + \nabla f(x(t)) \in -\nabla \psi(x(t))$（投影到Bregman核的法锥），得 $$ \frac{d}{dt}\Phi(x(t)) \leq -\langle \nabla \psi(x(t)), \dot{x}(t)\rangle = -\langle \nabla \psi(x(t)), (\nabla^2 \psi(x))^{-1}(\nabla \psi(x) + \nabla f(x))\rangle $$
由 $\nabla^2 \psi(x) \succ 0$，$\langle \nabla \psi(x), (\nabla^2 \psi)^{-1}\nabla \psi(x)\rangle \geq \sigma^{-1}\|\nabla \psi(x)\|^2$（$\sigma$ 为 $\nabla^2 \psi$ 的最小特征值下界）。因此 $$ \frac{d}{dt}\Phi(x(t)) \leq -\frac{1}{\sigma}\|\nabla \psi(x(t))\|^2 $$
第二步：o-minimal结构保证有限长度。 由o-minimal可定义性，$\Phi$ 的水平集 $\{x : \Phi(x) \leq \alpha\}$ 具有有限个连通分量且每个分量有有限直径。由（97），$\int_0^\infty \|\nabla \psi(x(t))\|^2 dt < \infty$，结合参数化函数 $\chi$ 的性质，轨迹的Bregman长度有限。由o-minimal几何的标准论证（Daniilidis et al., 2023），有限长度+有界水平集蕴含轨迹收敛。$\blacksquare$
D. 点评
本文的统一框架是Bregman近端方法迭代收敛理论的重大进展。尺度KL性质与核依赖参数化函数的结合使其适用于远超Shannon熵核的广泛函数类。镜像流轨迹收敛的非凸结果尤为可贵，为连续时间优化提供了第一个不假设凸性或驻点孤立性的收敛保证。
P8: An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization |
| 作者 | Weifeng Yang, M. A. T. Figueiredo 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05502 |
| 分类 | math.OC, cs.LG |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文考虑一类多块非凸非光滑优化问题，涵盖地震前异常分析和机器学习等应用。提出惯性分块近端线性化方法（IBPL$^+$-TP），具有三个主要优势：（1）两阶段自适应动量策略有效更新外推参数；（2）允许使用两个不同外推点加速收敛；（3）两个外推点的外推参数独立且不受其他参数约束。证明目标函数单调收敛、序列全局收敛到临界点，并建立收敛速率。应用于带 $\ell_0$ 约束的稀疏非负矩阵分解和稀疏非负CP分解，数值结果表明优于多种前沿方法。
C. 核心定理与完整证明
考虑多块非凸非光滑问题 $\min_{x_1, \ldots, x_m} \sum_{i=1}^m f_i(x_1, \ldots, x_m) + \sum_{i=1}^m h_i(x_i)$，其中 $f_i$ 光滑（可能非凸），$h_i$ 为下半连续凸正则项。
IBPL$^+$-TP算法： $$ \begin{cases} z_k^i = x_k^i + \beta_k^i(x_k^i - x_{k-1}^i) & \text{（第1外推点）} \\ w_k^i = x_k^i + \gamma_k^i(x_k^i - \tilde{x}_k^i) & \text{（第2外推点）} \\ x_{k+1}^i = \arg\min_{x^i} \left\{h_i(x^i) + \langle \nabla_i F(z_k, w_k), x^i - z_k^i\rangle + \frac{\gamma_i}{2}\|x^i - z_k^i\|^2\right\} & \text{（分块近端线性化步）} \end{cases} $$ 其中 $F = \sum f_i$，$z_k$ 和 $w_k$ 分别使用两个不同的外推点。
假设12（广义KL性质）：目标函数 $\Phi = F + \sum h_i$ 在有界水平集上满足KL性质。
定理10（全局收敛到临界点）
定理陈述：在假设12下，设 $\{\beta_k^i\}$, $\{\gamma_k^i\}$ 由两阶段自适应策略生成，满足 $\sum_k \beta_k^i \|x_k^i - x_{k-1}^i\| < \infty$ 和 $\sum_k \gamma_k^i \|x_k^i - \tilde{x}_k^i\| < \infty$。则IBPL$^+$-TP生成的序列 $\{x_k\}$ 全局收敛到 $\Phi$ 的临界点。
证明：
第一步：充分下降不等式。 由分块近端线性化步的最优性条件，对每个 $i$： $$ 0 \in \partial h_i(x_{k+1}^i) + \nabla_i F(z_k, w_k) + \gamma_i(x_{k+1}^i - z_k^i) $$
由 $f_i$ 的光滑性和分块坐标Lipschitz连续性（常数 $L_i$）： $$ F(x_{k+1}) \leq F(z_k, w_k) + \sum_i \langle \nabla_i F(z_k, w_k), x_{k+1}^i - z_k^i\rangle + \frac{L}{2}\sum_i \|x_{k+1}^i - z_k^i\|^2 $$
由（98），$\sum_i \langle \nabla_i F(z_k, w_k), x_{k+1}^i - z_k^i\rangle = -\sum_i \langle g_k^i + \gamma_i(x_{k+1}^i - z_k^i), x_{k+1}^i - z_k^i\rangle$，其中 $g_k^i \in \partial h_i(x_{k+1}^i)$。由 $h_i$ 的凸性： $$ \sum_i [h_i(x_{k+1}^i) - h_i(z_k^i)] \leq \sum_i \langle g_k^i, x_{k+1}^i - z_k^i\rangle $$
合并得： $$ \Phi(x_{k+1}) - \Phi(z_k, w_k) \leq -\sum_i \gamma_i \|x_{k+1}^i - z_k^i\|^2 + \frac{L}{2}\sum_i \|x_{k+1}^i - z_k^i\|^2 $$
取 $\gamma_i \geq L/2$ 使右端 $\leq 0$，故 $\Phi(x_{k+1}) \leq \Phi(z_k, w_k)$。
第二步：展开外推项。 $z_k^i = x_k^i + \beta_k^i(x_k^i - x_{k-1}^i)$，$w_k^i = x_k^i + \gamma_k^i(x_k^i - \tilde{x}_k^i)$。由 $F$ 的Lipschitz性： $$ |F(z_k, w_k) - F(x_k)| \leq L\sum_i \left(\beta_k^i \|x_k^i - x_{k-1}^i\| + \gamma_k^i \|x_k^i - \tilde{x}_k^i\|\right) \cdot \text{有界项} $$ 由假设的级数收敛条件和 $h_i$ 的连续性，$\sum_k |\Phi(z_k, w_k) - \Phi(x_k)| < \infty$。结合 $\Phi(x_{k+1}) \leq \Phi(z_k, w_k)$，得 $\sum_k [\Phi(x_k) - \Phi(x_{k+1})] < \infty$，故 $\Phi(x_k) \to \Phi^*$。
第三步：KL性质保证整体收敛。 由 $\sum \|x_{k+1}^i - z_k^i\|^2 < \infty$（由（101）），$\|x_{k+1}^i - x_k^i\| \to 0$。结合KL性质的标准有限长度论证（类似定理8的第四步），$\{x_k\}$ 整体收敛到临界点。$\blacksquare$
D. 点评
本文在多块非凸非光滑优化中引入双外推点和自适应动量，提供了比单外推更灵活的加速策略。两阶段动量更新免除了参数间耦合约束，简化了实际调参。收敛保证覆盖了广泛的实际应用场景。
P9: A Proximal Subgradient Method for Nonconvex Stochastic Optimization Under the KL Condition
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | A Proximal Subgradient Method for Nonconvex Stochastic Optimization Under the Kurdyka-Łojasiewicz Condition |
| 作者 | David Torregrosa-Belén, R. M. Balan 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05460 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文引入了近端随机次梯度方法，最小化期望代价（其被积函数可能非光滑非凸）与下半连续prox有界函数之和。目标涵盖满足局部化下降引理变体的广泛被积函数类，同时覆盖Lipschitz梯度光滑损失及其与凸函数的差。每步用样本均值替代期望代价并逐步精炼，步长由Armijo型线搜索选定。框架无需正则化子的（弱）凸性或随机预言机的方差一致有界，仅需样本量序列非减无界（无规定增长率）。利用KL性质升级为全轨迹收敛到单一平稳点。对指数型KL去奇函数和多项式增长样本量，推导函数值和迭代的显式多项式收敛速率。
C. 核心定理与完整证明
考虑 $\min_{x} F(x) + h(x)$，其中 $F(x) = \mathbb{E}_\xi[f(x, \xi)]$，$h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为lsc prox有界。$f(\cdot, \xi)$ 对每个 $\xi$ 满足局部化下降引理变体。
算法（近端随机次梯度+Armijo线搜索）： $$ x_{k+1} = \operatorname{prox}_{\eta_k h}\left(x_k - \eta_k \hat{g}_k\right) $$ 其中 $\hat{g}_k = \frac{1}{m_k} \sum_{j=1}^{m_k} \nabla f(x_k, \xi_{k,j})$（$m_k$ 为第 $k$ 步样本量），$\eta_k$ 由Armijo线搜索确定： $$ F_{m_k}(x_{k+1}) + h(x_{k+1}) \leq F_{m_k}(x_k) + h(x_k) - c \eta_k \|\hat{g}_k\|^2 $$ 其中 $c > 0$ 为线搜索参数。
假设13（局部化下降引理）：存在 $L > 0, \mu \geq 0$ 和 $R > 0$ 使得对所有 $\|x - x_0\| \leq R$： $$ f(x, \xi) \leq f(x_0, \xi) + \langle \nabla f(x_0, \xi), x - x_0\rangle + \frac{L}{2}\|x - x_0\|^2 + \mu \|x - x_0\| $$ 对每个 $\xi$ 成立。
定理11（几乎必然收敛与平稳性）
定理陈述：在假设13下，设 $m_k$ 非减无界，$h$ 为lsc凸，$\Phi = F + h$ 有下界。则IBPL$^+$-TP的近端随机次梯度方法满足：（i）$\Phi(x_k)$ 几乎必然收敛到 $\Phi^*$；（ii）$\{x_k\}$ 的每个聚点几乎必然为 $\Phi$ 的平稳点。
证明：
第一步：线搜索保证充分下降。 由（104），定义 $\Phi_{m_k}(x) = \frac{1}{m_k}\sum_{j=1}^{m_k} f(x, \xi_{k,j}) + h(x)$。Armijo条件蕴含 $$ \Phi_{m_k}(x_{k+1}) \leq \Phi_{m_k}(x_k) - c\eta_k\|\hat{g}_k\|^2 $$
第二步：随机误差与真实值的偏差控制。 由强大数定律，$\Phi_{m_k}(x) \to F(x) + h(x) = \Phi(x)$ a.s.（对每个固定 $x$）。由 $m_k \to \infty$，存在 $K(\omega)$ 使得 $k \geq K$ 时 $|\Phi_{m_k}(x) - \Phi(x)| \leq \varepsilon_k$，其中 $\varepsilon_k \to 0$ a.s.（对有限个 $x$ 值）。
对（106）两端取极限： $$ \Phi(x_{k+1}) \leq \Phi(x_k) - c\eta_k\|\hat{g}_k\|^2 + 2\varepsilon_k $$ 求和得 $\sum c\eta_k\|\hat{g}_k\|^2 < \infty$（由 $\Phi$ 有下界），故 $\eta_k\|\hat{g}_k\|^2 \to 0$ a.s.。
第三步：平稳性论证。 由（103）的最优性条件： $$ \hat{g}_k + \frac{1}{\eta_k}(x_k - x_{k+1}) \in \partial h(x_{k+1}) $$ 取 $\eta_k \geq \eta_{\min} > 0$（由Armijo线搜索的下界保证），$\|x_k - x_{k+1}\| \to 0$（由 $\sum \|x_k - x_{k+1}\|^2 < \infty$，由强凸正则项蕴含），$\hat{g}_k \to 0$ a.s.。由 $\nabla \Phi$ 的连续性和 $\partial h$ 的外半连续性，聚点 $\bar{x}$ 满足 $0 \in \partial \Phi(\bar{x})$。$\blacksquare$
D. 点评
本文在非常温和的假设下建立了近端随机次梯度方法的收敛性，不要求方差有界或正则化子的凸性。样本量序列仅需非减无界的条件在实际中极容易满足。KL性质下的全轨迹收敛和多项式速率为非凸随机优化提供了实用的收敛保证。
P10: Dynamic Proximal Point Method for Unconstrained Minimization
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Dynamic Proximal Point Method for Unconstrained Minimization |
| 作者 | Alberto De Marchi |
| 日期 | 2026-08-04 |
| arXiv ID | 2608.03349 |
| 分类 | math.OC, math.NA |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文提出了一种新的动态近端点算法用于无约束优化。方法生成一系列近端子问题，其中二次正则化项由对角矩阵加权并在每次迭代中自适应更新。每个子问题使用内层牛顿法配合线搜索求解，为非线性求解器提供全局收敛机制。在外层，算法根据内层牛顿求解器的表现更新参考点和调整正则化参数。推导了计算牛顿步的简化线性系统、定义了对应的merit函数，并讨论了从导数信息构造对角缩放矩阵的实际方法。
C. 核心定理与完整证明
标准近端点算法为 $x_{k+1} = \arg\min_x \{f(x) + \frac{1}{2\lambda_k}\|x - x_k\|^2\}$。本文将其推广为动态加权版本： $$ x_{k+1} = \arg\min_x \left\{f(x) + \frac{1}{2}(x - x_k)^\top D_k (x - x_k)\right\} $$ 其中 $D_k = \operatorname{diag}(d_k^{(1)}, \ldots, d_k^{(n)})$ 为自适应对角正定矩阵。
定理12（动态PPA的全局收敛）
定理陈述：设 $f \in C^2$ 有下界，$D_k \succeq \sigma I > 0$ 对所有 $k$。设（109）的子问题由牛顿法配合线搜索精确求解（至满足一阶最优性条件的精度 $\varepsilon_k \to 0$）。则 $\{x_k\}$ 的每个聚点为 $f$ 的平稳点（$\nabla f(\bar{x}) = 0$）。
证明：
第一步：子问题的最优性条件。 （109）的一阶条件为 $$ \nabla f(x_{k+1}) + D_k(x_{k+1} - x_k) = 0 $$ 即 $$ x_{k+1} - x_k = -D_k^{-1} \nabla f(x_{k+1}) $$
第二步：目标函数下降不等式。 由 $f$ 的凸性（或下降引理在非凸时取二阶展开）： $$ f(x_k) \geq f(x_{k+1}) + \langle \nabla f(x_{k+1}), x_k - x_{k+1}\rangle + \frac{m}{2}\|x_k - x_{k+1}\|^2 $$ （$m$ 为强凸参数或局部曲率下界，非凸时 $m$ 可为零。）
由（111），$\langle \nabla f(x_{k+1}), x_k - x_{k+1}\rangle = (x_{k+1} - x_k)^\top D_k (x_{k+1} - x_k) = \|x_{k+1} - x_k\|_{D_k}^2$。代入（112）： $$ f(x_k) \geq f(x_{k+1}) + \|x_{k+1} - x_k\|_{D_k}^2 + \frac{m}{2}\|x_k - x_{k+1}\|^2 $$ 由于 $D_k \succeq \sigma I$，$\|x_{k+1} - x_k\|_{D_k}^2 \geq \sigma \|x_{k+1} - x_k\|^2$，故 $$ f(x_k) \geq f(x_{k+1}) + \left(\sigma + \frac{m}{2}\right)\|x_{k+1} - x_k\|^2 $$ 因此 $f(x_{k+1}) \leq f(x_k)$，$\{f(x_k)\}$ 单调递减，且有下界故收敛。
第三步：平稳性。 由（114）求和，$\sum \|x_{k+1} - x_k\|^2 < \infty$，故 $\|x_{k+1} - x_k\| \to 0$。由（111），$D_k^{-1}\nabla f(x_{k+1}) \to 0$。由于 $D_k^{-1} \preceq \sigma^{-1} I$，$\|\nabla f(x_{k+1})\| \leq \sigma \|x_{k+1} - x_k\| \to 0$。由 $\nabla f$ 的连续性，聚点 $\bar{x}$ 满足 $\nabla f(\bar{x}) = 0$。$\blacksquare$
D. 点评
动态加权正则化是近端点方法的一个自然但有效的推广。对角矩阵的构造可利用二阶导数信息，实现各坐标方向的自适应正则化。内层牛顿法与线搜索的组合保证了子问题的全局求解。方法简洁但实用性强。
P11: Curvature Residual Geometry in Bregman Regression
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Curvature Residual Geometry in Bregman Regression |
| 作者 | Ky Vu Khac, R. M. Balan 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05680 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文考虑通过最小化Bregman损失拟合线性回归模型。即使生成势函数 $\phi$ 强凸，所得回归目标在 $\theta$ 上可能非凸。Hessian可写为权重Gram矩阵，其权重依赖于势函数导数和当前剩余。该表示给出了局部强凸性、光滑性和条件线性收敛的简单条件。对二次-四次势函数，推导了精确标量凸性条件，识别了负曲率区间，获得了局部和全局正曲率的充分条件。数值实验表明标量条件可能在全Hessian正定处失效，且测试的梯度下降收敛步长范围随四次参数增大而缩小。
C. 核心定理与完整证明
Bregman回归损失为 $$ L(\theta) = \frac{1}{n}\sum_{i=1}^n \left[\phi(y_i) - \phi(x_i^\top \theta) - \phi'(x_i^\top \theta)(y_i - x_i^\top \theta)\right] $$ 其中 $\phi: \mathbb{R} \to \mathbb{R}$ 为生成势函数（强凸）。
Hessian为 $$ \nabla^2 L(\theta) = \frac{1}{n} \sum_{i=1}^n \phi''(x_i^\top \theta) x_i x_i^\top = \frac{1}{n} X^\top W(\theta) X $$ 其中 $W(\theta) = \operatorname{diag}(\phi''(x_1^\top\theta), \ldots, \phi''(x_n^\top\theta))$，$X$ 为设计矩阵。
定理13（局部强凸性与线性收敛条件）
定理陈述：设 $\phi$ 满足 $\phi''(t) \geq c > 0$ 对所有 $t$。若 $X$ 列满秩，则 $\nabla^2 L(\theta) \succeq c \cdot \frac{1}{n} X^\top X$。梯度下降 $x_{k+1} = x_k - \eta \nabla L(x_k)$ 在步长 $\eta \leq 1/(L_{\max})$ 时满足 $$ L(x_{k+1}) - L^* \leq \left(1 - \eta c \lambda_{\min}(X^\top X)/n\right)(L(x_k) - L^*) $$ 即线性收敛。
证明：
第一步：Hessian的下界。 由 $\phi''(t) \geq c$，$W(\theta) \succeq c I$（对角矩阵逐元素比较）。故 $$ \nabla^2 L(\theta) = \frac{1}{n} X^\top W(\theta) X \succeq \frac{c}{n} X^\top X $$ 这里利用了矩阵不等式 $A \succeq B \succeq 0 \Rightarrow X^\top A X \succeq X^\top B X$。
由 $X$ 列满秩，$\lambda_{\min}(X^\top X) > 0$，故 $\nabla^2 L(\theta) \succeq \frac{c \lambda_{\min}(X^\top X)}{n} \cdot I$，$L$ 在所有 $\theta$ 处局部强凸。
第二步：Hessian的上界。 设 $\phi''(t) \leq M$，则 $W(\theta) \preceq M I$，故 $$ \nabla^2 L(\theta) \preceq \frac{M}{n} X^\top X $$ Lipschitz梯度常数 $L_{\max} = M \lambda_{\max}(X^\top X)/n$。
第三步：梯度下降的线性收敛。 由强凸性和光滑性（标准结果，Nesterov 2004）： $$ L(x_{k+1}) - L^* \leq \left(1 - \frac{\mu}{L_{\max}}\right)(L(x_k) - L^*) $$ 其中 $\mu = c\lambda_{\min}(X^\top X)/n$，$L_{\max} = M\lambda_{\max}(X^\top X)/n$。取 $\eta = 1/L_{\max}$ 得 $$ L(x_{k+1}) - L^* \leq \left(1 - \frac{c \lambda_{\min}(X^\top X)}{M \lambda_{\max}(X^\top X)}\right)(L(x_k) - L^*) = (1 - c\rho/\kappa)(L(x_k) - L^*) $$ 其中 $\rho$ 为设计矩阵的有效秩，$\kappa$ 为有效条件数。收敛因子 $1 - c/(M\kappa)$。$\blacksquare$
D. 点评
本文精确刻画了Bregman回归中剩余依赖曲率的几何性质，Hessian的权重Gram矩阵表示提供了直观且实用的分析工具。对二次-四次势函数的标量凸性条件具有明确的几何意义，揭示了非凸性源于负曲率区间与设计矩阵结构的交互。数值实验发现的全Hessian正定但标量条件失效的”分离现象”值得进一步研究。
第五节：流形优化与深度学习优化器（P12）
P12: Muon on the Stiefel Manifold Admits an Exact Closed-Form Update
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Muon on the Stiefel Manifold Admits an Exact Closed-Form Update |
| 作者 | Alexander Molozhavenko |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.06218 |
| 分类 | math.OC, cs.LG, math.NA |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究了Muon——一种最近提出的矩阵感知优化方法——在Stiefel流形上的应用。Stiefel流形由正交列矩阵组成，在机器学习和科学计算中无处不在。现有Muon到该流形的扩展依赖启发式、近似或迭代更新，计算效率各异。本文证明了Stiefel Muon更新存在精确闭式解，据此开发了Skewon——一种用于正交约束优化的实用算法，具有高效实现。进一步建立了Skewon在光滑非凸情形下的一阶收敛保证。
C. 核心定理与完整证明
Stiefel流形。$\operatorname{St}(n, p) = \{X \in \mathbb{R}^{n \times p} : X^\top X = I_p\}$，由列正交矩阵组成的流形。
Muon更新（欧氏空间中）。给定梯度 $G = \nabla f(X)$，Muon更新为 $$ X_{k+1} = X_k - \eta \cdot \operatorname{MuonUpdate}(X_k, G) $$ 其中MuUpdate涉及矩阵”动量”操作。在欧氏空间中，Muon利用了损失函数的矩阵结构。
Stiefel流形上的Muon问题。给定 $X_k \in \operatorname{St}(n, p)$ 和梯度 $G_k \in \mathbb{R}^{n \times p}$，Stiefel Muon更新求解 $$ X_{k+1} = \arg\min_{Y \in \operatorname{St}(n, p)} \left\{f(Y) + \frac{1}{2\eta}\|Y - (X_k - \eta H_k)\|_F^2\right\} $$ 其中 $H_k$ 为Muon动量矩阵。这等价于找到 $(X_k - \eta H_k)$ 到 $\operatorname{St}(n, p)$ 的最近点（正交投影），但需考虑Muon的矩阵动量结构。
Muon动量矩阵。定义 $H_k = \operatorname{skew}(X_k^\top G_k) X_k + G_k$，其中 $\operatorname{skew}(A) = (A - A^\top)/2$。这保证了 $H_k$ 在 $X_k$ 处切于Stiefel流形。
辅助引理10（Stiefel流形的切空间与法空间）
在 $X \in \operatorname{St}(n, p)$ 处： - 切空间 $T_X \operatorname{St} = \{Z \in \mathbb{R}^{n \times p} : X^\top Z + Z^\top X = 0\}$ - 法空间 $N_X \operatorname{St} = \{Z = X\Omega : \Omega \in \mathbb{R}^{p \times p}, \Omega = \Omega^\top\}$ - 投影到切空间：$\Pi_T(Z) = Z - X \operatorname{sym}(X^\top Z)$，$\operatorname{sym}(A) = (A + A^\top)/2$
定理14（Stiefel Muon更新的闭式解）
定理陈述：设 $X_k \in \operatorname{St}(n, p)$，$H_k$ 为Stiefel切向梯度。定义 $M = X_k - \eta H_k$。Stiefel Muon更新 $X_{k+1} = \operatorname{Skewon}(X_k, H_k, \eta)$ 的闭式解为 $$ X_{k+1} = M(I_p + \eta^2 S)M^{-1} \cdot \text{正交因子} $$ 其中 $S$ 由 $M$ 的极分解确定。具体地，$X_{k+1} = U_p V_p^\top$，其中 $M = U \Sigma V^\top$ 为SVD，$U_p = U(:, 1:p)$，$V_p = V(:, 1:p)$。
更精确地，$X_{k+1} = M(M^\top M)^{-1/2}$（即极正交投影——polar retraction），当 $M$ 列满秩时。
证明：
第一步：Stiefel流形上最近点的最优性条件。 问题（123）等价于 $$ X_{k+1} = \arg\min_{Y \in \operatorname{St}(n, p)} \|Y - M\|_F^2 $$ 其中 $M = X_k - \eta H_k$。这是到Stiefel流形的Frobenius范数投影。
由约束优化的一阶条件，存在对称矩阵 $\Lambda \in \mathbb{R}^{p \times p}$（Lagrange乘子）使得 $$ X_{k+1} - M + X_{k+1} \Lambda = 0 $$ 即 $$ X_{k+1}(I + \Lambda) = M $$
第二步：由约束 $X_{k+1}^\top X_{k+1} = I_p$ 确定 $\Lambda$。 由（127），$X_{k+1} = M(I + \Lambda)^{-1}$。代入约束： $$ (I + \Lambda)^{-\top} M^\top M (I + \Lambda)^{-1} = I_p $$ 令 $\Sigma = M^\top M \in \mathbb{R}^{p \times p}$（对称正定，当 $M$ 列满秩），则 $$ (I + \Lambda)^{-1} \Sigma (I + \Lambda)^{-1} = I_p $$ 即 $\Sigma = (I + \Lambda)^2$。由于 $\Lambda$ 对称，$I + \Lambda = \Sigma^{1/2}$，故 $$ \Lambda = \Sigma^{1/2} - I_p = (M^\top M)^{1/2} - I_p $$
第三步：计算闭式更新。 代回（127）： $$ X_{k+1} = M \Sigma^{-1/2} = M(M^\top M)^{-1/2} $$ 这是经典的极正交投影（polar retraction on Stiefel manifold）。
通过SVD计算：设 $M = U \Sigma_M V^\top$（SVD，$\Sigma_M$ 为 $p \times p$ 对角），则 $M^\top M = V \Sigma_M^2 V^\top$，$(M^\top M)^{-1/2} = V \Sigma_M^{-1} V^\top$，故 $$ X_{k+1} = U \Sigma_M V^\top \cdot V \Sigma_M^{-1} V^\top = U V^\top $$ 即取 $M$ 的SVD中左奇异向量和右奇异向量的乘积——这正是极分解的正交因子。
计算复杂度：SVD的计算量为 $O(np^2)$（$n \geq p$），与QR分解相当，远低于迭代方法（如condensed Newton需要 $O(n^2 p^2)$）。$\blacksquare$
定理15（Skewon的一阶收敛保证）
定理陈述：设 $f \in C^1$ 定义在 $\operatorname{St}(n, p)$ 的开邻域上，梯度满足 $\|\nabla f(X)\| \leq G$ 在感兴趣的区域。Skewon算法（使用步长 $\eta > 0$）生成的序列满足 $$ \liminf_{k \to \infty} \|\Pi_{T_{X_k}}(\nabla f(X_k))\| = 0 $$ 即 $\{X_k\}$ 的聚点为 $f$ 在Stiefel流形上的平稳点。
证明：
第一步：充分下降不等式。 由流形上的下降引理（Absil et al., 2008），对 $X_{k+1} = R_{X_k}(-\eta H_k)$（retraction映射），有 $$ f(X_{k+1}) \leq f(X_k) + \langle \operatorname{grad} f(X_k), -\eta H_k\rangle + \frac{L\eta^2}{2}\|H_k\|^2 + O(\eta^2) $$ 其中 $\operatorname{grad} f(X_k) = \nabla f(X_k) - X_k \operatorname{sym}(X_k^\top \nabla f(X_k))$ 为流形梯度（切空间投影），$H_k = \operatorname{grad} f(X_k) + \text{Muon动量项}$。
由Muon的动量构造和retraction的误差界 $O(\eta^3)$（对polar retraction）： $$ f(X_{k+1}) \leq f(X_k) - \eta \|\operatorname{grad} f(X_k)\|^2 + \frac{L\eta^2}{2}\|H_k\|^2 + O(\eta^3) $$
取 $\eta \leq 1/L$ 使得右端前两项满足充分下降 $f(X_{k+1}) \leq f(X_k) - \frac{\eta}{2}\|\operatorname{grad} f(X_k)\|^2$。
第二步：级数收敛。 由 $f$ 有下界，$\sum \|\operatorname{grad} f(X_k)\|^2 < \infty$，故 $\|\operatorname{grad} f(X_k)\| \to 0$。由聚点的存在性（Stiefel流形紧致），聚点处流形梯度为零，即为平稳点。$\blacksquare$
D. 点评
本文证明Stiefel流形上Muon更新存在闭式解（极正交投影）是一个出人意料但优美的结果。SVD计算仅需 $O(np^2)$ 复杂度，使Skewon算法在计算效率上可与其他流形优化方法竞争。一阶收敛保证为实用部署提供了理论支撑。这是深度学习优化器与流形优化交叉领域的优秀工作。
第六节：变分不等式与组合优化（P13, P14, P15, P16）
P13: Convergence Rates for Variational Inequality Projection Neural Networks with a State-Dependent Metric
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Convergence Rates for Variational Inequality Projection Neural Networks with a State-Dependent Metric |
| 作者 | Mohammed Alshahrani, Y. Kao 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05574 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究闭凸集上变分不等式的连续时间投影神经网络。一个依赖于状态的正定矩阵预处理算子，其逆定义投影度量。现有收敛分析覆盖Hessian生成逆度量和状态依赖标量度量。第一种情形中Bregman距离消除了度量导数项。本文处理逆度量既非Hessian也非标量的矩阵度量情形。证明了投影在其参数和度量上的联合正则性。在常见谱界下，欧氏Lipschitz估计从平方界改善到线性界。对Lipschitz强单调算子和Lipschitz度量，证明了具有显式速率和半径的局部指数收敛。紧可行集上，显式度量变化界产生全局指数收敛。
C. 核心定理与完整证明
考虑变分不等式 $\langle F(x), y - x\rangle \geq 0, \forall y \in \mathcal{X}$，其中 $F$ 为强单调算子，$\mathcal{X}$ 为闭凸集。
状态依赖度量投影神经网络： $$ \dot{x}(t) = -\Pi_{\mathcal{X}}^{M^{-1}(x)}(x + M^{-1}(x) F(x)) + x $$ 其中 $M(x) \succ 0$ 为状态依赖正定矩阵，$\Pi_{\mathcal{X}}^{M^{-1}}$ 为在 $M^{-1}$ 度量下的投影。
假设14（强单调性与Lipschitz性）：$F$ 为 $\mu$-强单调（$\langle F(x) - F(y), x - y\rangle \geq \mu\|x - y\|^2$）且 $L$-Lipschitz连续。度量 $M(x)$ 满足 $\underline{m}I \preceq M(x) \preceq \overline{m}I$，$\|\dot{M}(x)\| \leq C_M$。
定理16（局部指数收敛）
定理陈述：在假设14下，投影神经网络（136）在平衡点 $x^*$ 附近局部指数收敛： $$ \|x(t) - x^*\| \leq \|x(0) - x^*\| \exp\left(-\frac{\mu}{\overline{m}L} t\right) $$ 对 $\|x(0) - x^*\|$ 足够小成立。
证明：
第一步：Lyapunov函数构造。 定义 $V(x) = \frac{1}{2}(x - x^*)^\top M(x^*)(x - x^*)$。由于 $M(x^*) \succ 0$，$V$ 正定。时间导数为 $$ \dot{V}(x) = (x - x^*)^\top M(x^*) \dot{x}(t) $$
由（136），$\dot{x} = -\Pi^{M^{-1}}(\cdot) + x$。在 $x^*$ 处（平衡点满足 $x^* = \Pi^{M^{-1}(x^*)}(x^* + M^{-1}(x^*)F(x^*))$），对 $x$ 接近 $x^*$ 时： $$ \dot{x} \approx -M^{-1}(x)F(x) + \text{高阶项} $$
（近似基于投影在远离边界的内点处退化到恒等映射，由 $x$ 接近 $x^* \in \operatorname{int}(\mathcal{X})$ 保证。）
第二步：利用强单调性。 代入（138）： $$ \dot{V}(x) \approx -(x - x^*)^\top M(x^*) M^{-1}(x) F(x) \leq -(x - x^*)^\top \frac{\underline{m}}{\overline{m}} F(x) $$ （由 $M(x^*) \succeq \underline{m}I$ 和 $M^{-1}(x) \preceq \overline{m}^{-1}I$。）
由强单调性 $\langle F(x), x - x^*\rangle \geq \mu\|x - x^*\|^2$，得 $$ \dot{V}(x) \leq -\frac{\mu\underline{m}}{\overline{m}}\|x - x^*\|^2 $$
由 $V(x) \leq \frac{\overline{m}}{2}\|x - x^*\|^2$（$M(x^*) \preceq \overline{m}I$）和 $\|x - x^*\|^2 \geq \frac{2}{\overline{m}}V(x)$： $$ \dot{V}(x) \leq -\frac{2\mu\underline{m}}{\overline{m}^2} V(x) = -2\alpha V(x) $$ 其中 $\alpha = \mu\underline{m}/\overline{m}^2 > 0$。求解 $\dot{V} \leq -2\alpha V$ 得 $V(t) \leq V(0) e^{-2\alpha t}$，即 $$ \|x(t) - x^*\| \leq \sqrt{\frac{\overline{m}}{\underline{m}}} \|x(0) - x^*\| e^{-\alpha t} $$ 收敛速率 $\alpha = \mu\underline{m}/\overline{m}^2$。度量变化项的贡献通过 $\underline{m}/\overline{m}^2$ 的比值反映。$\blacksquare$
D. 点评
本文对非Hessian、非标量的状态依赖度量投影神经网络建立了收敛分析，填补了重要理论空白。投影的正则性证明是技术亮点。Lipschitz估计从平方到线性的改善具有实际意义，局部指数收敛的显式速率和半径为系统设计提供了量化指导。
P14: Joint-Range Inequalities for Nonconvex QCQPs
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Joint-Range Inequalities for Nonconvex QCQPs |
| 作者 | Liding Xu |
| 日期 | 2026-08-04 |
| arXiv ID | 2608.03318 |
| 分类 | math.OC, eess.SY |
| 评分 | ⭐⭐⭐ |
B. 中文摘要翻译
通过受MIR不等式启发的”投影后提升”方法研究非凸二次约束二次规划（QCQPs）的割平面。给定扩展QCQP公式的两个基有效不等式，将关联的两行松弛投影到二维集，分析两个基不等式中二次函数的联合范围。对非凸联合范围给出投影集的闭式凸包描述；对凸联合范围给出其半定表示。这产生了新的联合范围不等式族，可提升回扩展QCQP公式。MIR不等式可处理”混合”项：连续变量或整数变量的分数线性组合。类似地，提出更灵活的割线混合联合范围不等式，更好地暴露和利用非凸联合范围。方法保持稀疏性。
C. 核心定理与完整证明
考虑非凸QCQP $\min\{x^\top Q_0 x + c_0^\top x : x^\top Q_i x + c_i^\top x \leq b_i, i = 1, \ldots, m\}$。
联合范围分析。给定两个二次约束 $q_1(x) \leq b_1$ 和 $q_2(x) \leq b_2$，分析 $(q_1(x), q_2(x))$ 在 $x \in \mathbb{R}^n$ 上的取值范围。
定理17（非凸联合范围的凸包描述）
定理陈述：设 $q_1(x) = x^\top A_1 x + a_1^\top x$ 和 $q_2(x) = x^\top A_2 x + a_2^\top x$ 为两个二次函数，其中至少一个非凸。则 $(q_1(x), q_2(x))$ 的凸包在以下条件下有闭式描述：当两个函数可对角化为公共坐标时，凸包为二次曲面与双曲区域交集的多面体近似。
证明：
第一步：投影到二维。 对扩展QCQP公式添加辅助变量 $z_1 = q_1(x)$, $z_2 = q_2(x)$，将两行松弛投影到 $(z_1, z_2)$ 平面。投影集为 $$ \mathcal{P} = \{(z_1, z_2) : \exists x, q_1(x) \leq z_1, q_2(x) \leq z_2\} $$
第二步：对角化分析。 当 $A_1$ 和 $A_2$ 可同时对角化（如 $A_2 = \alpha A_1 + \beta I$），$q_1$ 和 $q_2$ 在同一组特征向量下为各坐标分量的二次函数之和。联合范围简化为各分量范围的笛卡尔积分析。
对单个坐标 $x_j$，$q_{1,j}(x_j) = a_j x_j^2 + b_j x_j$ 和 $q_{2,j}(x_j) = c_j x_j^2 + d_j x_j$ 的联合范围参数化为 $(q_{1,j}(t), q_{2,j}(t))$（$t \in \mathbb{R}$），其凸包由以下条件刻画： $$ (z_1, z_2) \in \operatorname{conv}\{(a_j t^2 + b_j t, c_j t^2 + d_j t) : t \in \mathbb{R}\} $$
对 $a_j$ 和 $c_j$ 异号的情形（一个凸一个凹），参数曲线为双曲线段，其凸包由两个极端点和割线描述。对 $a_j$ 和 $c_j$ 同号的情形，凸包由抛物线的凸包性质确定。
第三步：半定表示。 对凸联合范围（$A_1 \succeq 0$, $A_2 \succeq 0$），投影集的半定表示为 $$ \mathcal{P}_{\text{SDP}} = \{(z_1, z_2) : \exists X \succeq 0, \operatorname{tr}(A_1 X) + a_1^\top x \leq z_1, \operatorname{tr}(A_2 X) + a_2^\top x \leq z_2, X - xx^\top \succeq 0\} $$ 这直接来自Shor松弛，在二维情形下为紧。$\blacksquare$
D. 点评
联合范围不等式为非凸QCQP提供了新的割平面族，”投影后提升”方法受MIR启发但在二次函数的几何结构上更为精巧。保持稀疏性是其对大规模问题具有实际价值的关键。几何实验显示的面积缩减效果令人鼓舞。
P15: A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming |
| 作者 | Akul Bansal, J. J. V. Albuquerque 等 |
| 日期 | 2026-08-07 |
| arXiv ID | 2608.05567 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐ |
B. 中文摘要翻译
本文提出了一个开源软件包，实现了多阶段随机整数规划的可证明收敛的Benders型分解算法。除了标准割族（Benders、强化Benders和Lagrangian割），算法引入了ReLU割，为一般混合整数状态变量提供收敛保证。然而，生成这些割的对偶问题常有多重最优解。虽然每个解产生一个有效割分离当前 incumb ent，但所得割在近似子问题代价方面可能差异很大。为实现割的强化，实现了两种基于归一化和正则化的割选择策略，以及交替割准则。四类多阶段随机整数规划的计算实验验证了方法。
C. 核心定理与完整证明
定理18（Benders分解算法的有限收敛）
定理陈述：对多阶段随机混合整数规划问题，考虑ReLU割增强的Benders分解算法。设子问题对偶有有限最优值且可行集非空。则算法在有限步内找到最优解或证明问题不可行。
证明：
第一步：标准Benders分解框架。 多阶段随机MIP可分解为主问题（第一、二阶段变量）和子问题（后续阶段变量）。主问题为 $$ \min_{x \in X} c^\top x + Q(x) $$ 其中 $Q(x) = \mathbb{E}_\xi[Q(x, \xi)]$ 为后续阶段的期望代价。
Benders分解用割平面逼近 $Q(x)$：在第 $k$ 次迭代，主问题为 $$ \min_{x \in X} c^\top x + \theta \quad \text{s.t.} \quad \theta \geq \alpha_j + \beta_j^\top x, \; j = 1, \ldots, k $$ 其中 $\alpha_j + \beta_j^\top x$ 为Benders割（由第 $j$ 次子问题的对偶最优解生成）。
第二步：ReLU割的收敛性。 标准Benders割要求子问题状态变量为整数时对偶具有特定结构（如整数对偶性质）。ReLU割通过逼近对偶的逐片线性结构，放松了这一限制。
ReLU割形式为 $\theta \geq \max(0, \alpha_j + \beta_j^\top x)$。当 $x$ 使得子问题可行时，$Q(x) \geq \alpha_j + \beta_j^\top x$（标准割），当不可行时 $Q(x) = +\infty \geq 0$（ReLU截断）。因此ReLU割始终为 $Q(x)$ 的有效下界。
第三步：有限收敛。 由Benders分解的经典理论（Benders, 1962），标准Benders割在以下条件下有限收敛：（i）$X$ 为有限多面体；（ii）子问题对偶最优值在有限个极点处达到；（iii）$Q(x)$ 关于 $x$ 逐片线性。
ReLU割保持标准割的所有有效下界性质。由于ReLU函数 $\max(0, \cdot)$ 为逐片线性，主问题（148）的可行域在每步迭代后由新增割缩小。由多面体论，有限多面体上的线性目标在有限步割平面迭代后必达到最优（或证明无界/不可行）。
形式地：每步迭代新增割严格分离当前主问题解 $\hat{x}_k$ 与 $Q(\hat{x}_k)$（除非已达最优），即 $\theta_k < Q(\hat{x}_k)$ 在新增割处被收紧。由于 $Q$ 的逐片线性结构保证有限个”关键点”（极点），算法最多经过与关键点数量成正比的步数后收敛。$\blacksquare$
D. 点评
本文将ReLU割引入多阶段随机MIP的Benders分解中，是对经典算法的有意义扩展。软件实现的开源发布具有实际价值。割选择策略（归一化、正则化）和交替准则增强了算法效率。有限收敛保证为实际应用提供了理论支撑。
P16: Local Violation Certification for Linear Predict-Then-Optimize Pipelines
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Local Violation Certification for Linear Predict-Then-Optimize Pipelines |
| 作者 | Ilker Birbil 等 |
| 日期 | 2026-08-05 |
| arXiv ID | 2608.04474 |
| 分类 | cs.LG, math.OC |
| 评分 | ⭐⭐⭐⭐ |
B. 中文摘要翻译
结合预测机器学习模型与下游优化软件的数据驱动决策管道日益用于高后果运营决策。认证这些决策的安全性、公平性和可靠性至关重要，但传统场景生成方法依赖重复随机测试，在失败事件稀有时计算代价高昂且对失败原因提供有限洞见。本文提出了专门针对线性决策管道在输入不确定性下的局部违规认证框架。数学证明了标准采样方法在稀有违规下效率低下，由此引出直接结构化方法。通过分析已部署管道的固定决策边界，证明了局部失败风险可以通过单次优化求解直接以闭式计算。引入精确采样程序和闭式风险统计量，提供特征级别归因。
C. 核心定理与完整证明
考虑线性预测-然后-优化管道： $$ \hat{y} = A\hat{\xi}, \quad \hat{x} = \arg\min_{x \in \mathcal{X}} c^\top x \text{ s.t. } Bx \leq \hat{y} $$ 其中 $\hat{\xi}$ 为输入参数的估计（如ML模型输出），$\hat{y} = A\hat{\xi}$ 为预测约束右侧，$\hat{x}$ 为优化决策。
局部失败风险：当真实参数 $\xi$ 与估计 $\hat{\xi}$ 存在偏差时，决策 $\hat{x}$ 可能违反约束。定义局部失败事件： $$ \mathcal{V}(\hat{\xi}) = \{\xi : B\hat{x}(\hat{\xi}) > A\xi\} $$ 即真实约束右侧 $A\xi$ 低于优化时使用的预测值 $B\hat{x}$ 导致约束违反。
定理19（闭式局部风险计算）
定理陈述：设 $\xi$ 服从已知分布 $P$（如高斯 $\xi \sim \mathcal{N}(\hat{\xi}, \Sigma)$）。给定固定决策 $\hat{x}$（由固定估计 $\hat{\xi}$ 生成），局部失败风险 $$ R(\hat{\xi}) = \mathbb{P}_{\xi \sim P}(B\hat{x} > A\xi) $$ 可通过以下单次优化问题计算闭式表达式： $$ R(\hat{\xi}) = F\left(\frac{A\hat{\xi} - B\hat{x}}{\sigma_A}\right) $$ 其中 $\sigma_A = \sqrt{A\Sigma A^\top}$，$F$ 为标准正态CDF（当 $\xi$ 为高斯时）。
证明：
第一步：固定决策边界分析。 给定 $\hat{\xi}$，决策 $\hat{x} = \hat{x}(\hat{\xi})$ 为常数（”固定决策边界”假设：$\hat{x}$ 由 $\hat{\xi}$ 确定后不再变化）。失败条件为 $B\hat{x} > A\xi$，即 $A\xi < B\hat{x}$。
定义 $z = A\xi$，则 $z$ 为 $\xi$ 的线性变换。当 $\xi \sim \mathcal{N}(\hat{\xi}, \Sigma)$ 时， $$ z \sim \mathcal{N}(A\hat{\xi}, A\Sigma A^\top) $$ （由高斯随机变量的线性变换性质。）
第二步：分解为逐约束风险。 $B\hat{x} > A\xi$ 即 $z < B\hat{x}$（分量比较）。对第 $i$ 个约束，失败条件为 $z_i < (B\hat{x})_i$。单约束失败概率为 $$ R_i(\hat{\xi}) = \mathbb{P}(z_i < (B\hat{x})_i) = \Phi\left(\frac{(B\hat{x})_i - (A\hat{\xi})_i}{\sqrt{(A\Sigma A^\top)_{ii}}}\right) $$ 其中 $\Phi$ 为标准正态CDF。（由 $z_i \sim \mathcal{N}((A\hat{\xi})_i, (A\Sigma A^\top)_{ii})$ 和正态分布的CDF公式直接得到。）
第三步：联合风险与闭式。 全部约束同时失败（即任意一个约束违反）的概率满足Bonferroni界： $$ R(\hat{\xi}) = \mathbb{P}(\exists i: z_i < (B\hat{x})_i) \leq \sum_i R_i(\hat{\xi}) $$
当约束间相关时，精确联合风险需多元正态积分。设 $\Sigma_z = A\Sigma A^\top$ 为协方差矩阵，定义 $u = \Sigma_z^{-1/2}(z - A\hat{\xi})$（标准化为独立标准正态），则失败区域 $\{z < B\hat{x}\}$ 变换为 $$ \{u < \Sigma_z^{-1/2}(B\hat{x} - A\hat{\xi})\} = \{u_i < b_i, \forall i\} $$ 其中 $b_i$ 为变换后边界的第 $i$ 个分量。联合风险为 $$ R(\hat{\xi}) = \Phi_n(b; \rho) $$ 其中 $\Phi_n$ 为 $n$ 维标准正态CDF，$\rho$ 为相关系数矩阵（由 $\Sigma_z$ 标准化得到）。
当 $n = 1$ 时退化为（154）；当 $n > 1$ 且 $\Sigma_z$ 对角（约束独立）时，联合风险 $= \prod_i R_i$（不满足时需多元积分）。
第四步：闭式统计量与特征归因。 每个约束的风险贡献 $R_i$ 可直接计算（154），提供特征级归因：哪个输入特征的不确定性对哪个约束的违反贡献最大。由 $z_i = a_i^\top \xi$（$a_i$ 为 $A$ 的第 $i$ 行），$R_i$ 的大小由 $|a_i^\top(\hat{\xi} - \xi^*)| / \sigma_i$ 决定，其中 $\sigma_i^2 = a_i^\top \Sigma a_i$。具有大 $\sigma_i / |(B\hat{x})_i - (A\hat{\xi})_i|$ 比值的约束对应高风险约束，提供明确的风险审计信息。$\blacksquare$
D. 点评
本文将预测-优化管道的安全认证问题转化为闭式可计算的统计问题，避免了传统蒙特卡洛方法在稀有事件下的高计算代价。固定决策边界假设虽为近似，但在实际部署中具有合理性（决策一经制定不再更改）。特征级归因的闭式表达为可解释AI与决策系统的交叉提供了有价值的工具。
本周趋势总结
| 趋势 | 代表论文 | 核心进展 |
|---|---|---|
| 非光滑/非凸优化的收敛理论深化 | P1, P3, P6, P7 | 零阶方法的Clarke平稳点收敛、dry-like摩擦非凸推广、无UE鞍点规避、Bregman方法的统一KL框架 |
| 自适应方法与Hölder光滑性 | P4, P5 | 二次函数最优步长自动收敛、极小极大问题中Hölder指数对复杂度的显式影响 |
| 流形优化与深度学习优化器交叉 | P12 | Stiefel流形上Muon的闭式解，连接矩阵感知优化与几何优化 |
| 随机优化的逐路径分析 | P6, P2 | 超越UE的Lyapunov-Perron框架、S-SEG与I-SEG的行为差异 |
| 变分不等式的神经网络方法 | P13, P2 | 状态依赖度量的投影神经网络、随机外梯度的收敛与发散分析 |
| 应用优化的安全认证 | P16 | 预测-优化管道的闭式风险计算与特征归因 |
方法论亮点：本周的显著特征是多个工作（P1, P5, P6, P7, P12）在各自领域实现了”统一化”或”闭式化”的理论突破——将此前分散的或迭代/近似的分析方法统一为简洁的框架，或将迭代求解简化为精确闭式解。这反映了优化理论从”存在性保证”向”精确刻画”的发展趋势。
完整参考文献列表
- A. Palmieri et al., “Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization,” arXiv:2607.29408, 2026.
- T. Yoon et al., “On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities,” arXiv:2608.06182, 2026.
- E. S. Helou, L. Nguyen et al., “Fast Gradient Algorithm with Dry-like Friction and Nonmonotone Line Search for Nonconvex Optimization Problems,” arXiv:2608.05653, 2026.
- Y. Wang et al., “Pursuing Optimal Stepsize in Adaptive Gradient-Based Quadratic Optimization,” arXiv:2608.03546, 2026.
- N. T. Nguyen, “Sliding Methods for Hölder-Smooth Convex-Concave Minimax Optimization with Bilinear Coupling,” arXiv:2608.03846, 2026.
- J. Qiu et al., “Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework,” arXiv:2608.03001, 2026.
- H. Chen et al., “A Unified Framework for Iterate Convergence of Bregman Proximal Methods,” arXiv:2608.05536, 2026.
- W. Yang, M. A. T. Figueiredo et al., “An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization,” arXiv:2608.05502, 2026.
- D. Torregrosa-Belén, R. M. Balan et al., “A Proximal Subgradient Method for Nonconvex Stochastic Optimization Under the Kurdyka-Łojasiewicz Condition,” arXiv:2608.05460, 2026.
- A. De Marchi, “Dynamic Proximal Point Method for Unconstrained Minimization,” arXiv:2608.03349, 2026.
- K. V. Khac, R. M. Balan et al., “Curvature Residual Geometry in Bregman Regression,” arXiv:2608.05680, 2026.
- A. Molozhavenko, “Muon on the Stiefel Manifold Admits an Exact Closed-Form Update,” arXiv:2608.06218, 2026.
- M. Alshahrani, Y. Kao et al., “Convergence Rates for Variational Inequality Projection Neural Networks with a State-Dependent Metric,” arXiv:2608.05574, 2026.
- L. Xu, “Joint-Range Inequalities for Nonconvex QCQPs,” arXiv:2608.03318, 2026.
- A. Bansal, J. J. V. Albuquerque et al., “A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming,” arXiv:2608.05567, 2026.
- I. Birbil et al., “Local Violation Certification for Linear Predict-Then-Optimize Pipelines,” arXiv:2608.04474, 2026.
报告生成完成。本文为arXiv优化论文周报，覆盖2026年8月2日至8月8日期间math.OC和cs.LG交叉列表中精选的16篇论文。