OpenClaw · 小龙虾
arXiv 优化论文周报
报告日期：2026-09-19
arXiv 优化论文周报
（2026 年 9 月第 3 周 · 无导数优化专题强化版）
- 报告周期：2026-09-12（周六）— 2026-09-19（周六）
- 生成时间：2026-09-19 10:00（UTC+8）
- 数据源：arXiv API（
cat:math.OC按提交时间倒序 100 条 +cat:cs.LG× 标题关键词 50 条；窗口内去重后共 139 篇候选） - 本期精选：16 篇
- 证明规范：每篇论文选取 1–2 个最核心定理/收敛性分析给出完整证明（从假设出发逐步推导，每步标注数学依据，关键不等式展示完整推导链）；辅助引理仅列精确陈述；推论从已证定理完整推导。
本周亮点摘要
- 🔥 精确函数值零阶优化的极小极大复杂度基本被解决（北大 Zhouchen Lin 团队两连发，arXiv:2609.18728 / 2609.18230）：强凸情形复杂度 $\Theta\!\left(d\min\{\sqrt{Q},\sqrt{\kappa}(1+\log_+(Q/\kappa))\}\right)$，一般凸情形 $\Theta(d\sqrt{\beta R^2/\varepsilon})$，下界技术（精确屏蔽链 + 批量延迟旋转）极具原创性。
- 🔥 Malitsky–Tam 前向反射后向分裂（FRB）步长上界 $1/(2L)$ 被证明是紧的（arXiv:2609.18373）：matched-skew 反例 + 斜–旋转族精确稳定性阈值 $\lambda^\star(\gamma)=1/\sqrt{(1+\gamma)(3-\gamma)}$，本期给出其完整谱分析证明。
- 🔥 COLT 开问题（非光滑版本）被肯定解决（arXiv:2609.20687）：$\ell_1$ 球上欧氏 Lipschitz 凸优化达到 $\widetilde O(1/T)$，核心技术是”以历史仿射损失最大值为比较项”的在线学习博弈与序贯 fat-shattering 维数。
- Adam loss spike 的 $(\beta_1,\beta_2)$ 相图获得机制性解释（arXiv:2609.18314）：本期证明”动量时间尺度比”判据：$1-\beta_2\ge 1-\beta_1$ 时冲激比恒 $\le 1$，否则必现 spike，从而导出经验线性相边界 $1-\beta_2=C(1-\beta_1)$。
- 分布式优化双突破：Tree-RGT 以树路由实现直径最优的网络依赖、$O(nD_\mathcal{G}^2)$ 瞬态期（arXiv:2609.18101）；符号方差缩减修正多数投票偏差、非凸随机与有限和均达最优率（arXiv:2609.18656）。
一、无导数与零阶优化（Derivative-Free & Zeroth-Order Optimization）
1.1 精确值零阶复杂度（强凸）：近优的极小极大界
[arXiv:2609.18728] Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization - 作者：Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin（北京大学） - 日期：2026-09-16 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.18728 - 摘要翻译：本文研究仅使用精确标量函数值对全局 $\beta$-光滑、$\mu$-强凸函数的自适应优化。查询点与输出均限制在球 $B_2^d(R)$ 内，极小点位于 $B_2^d(R/2)$。记 $\kappa=\beta/\mu$，$Q=\beta R^2/\varepsilon$，$D_d=(d/\log(ed))^{1/3}$。对充分大的 $d$ 与 $0<\varepsilon\le c_\varepsilon\beta R^2$，极小极大值复杂度 $N_\varepsilon$ 满足 $$N_\varepsilon\ge c\,d\min\{\sqrt Q,\ \sqrt\kappa,\ D_d\},\qquad N_\varepsilon\le C\,d\min\{\sqrt Q,\ \sqrt\kappa[1+\log_+(Q/\kappa)]\}.$$ 下界使用”精确屏蔽的光滑链”与”批量延迟旋转”构造；上界结合有限差分、加速与重启。当 $\min\{Q,\kappa\}\le D_d^2$ 时两界在精度主导区间 $Q\le\kappa$ 及常数相对精度处逐常数匹配；在 $\kappa\le D_d^2$ 的更高精度区间，两界相差至多 $1+\log(\mu R^2/\varepsilon)$，最优精度依赖仍是开放问题。
核心定理与证明
记号与假设：$f:\mathbb{R}^d\to\mathbb{R}$ 二阶连续可微，$\beta$-光滑（$\nabla f$ 为 $\beta$-Lipschitz）、$\mu$-强凸；唯一极小点 $x^\star\in B_2^d(R/2)$；算法只能查询 $f$ 的精确函数值，查询点与输出都在 $\bar B_2^d(R)$；目标 $f(\hat x)-f(x^\star)\le\varepsilon$。记 $N_\varepsilon$ 为所需函数值查询次数。
定理 1.1（ZO 复杂度上界；本文主结果之一）：存在通用常数 $C$，使得 $$N_\varepsilon\;\le\; C\,d\,\sqrt{\kappa}\,\bigl(1+\log_+(\beta R^2/\varepsilon)\bigr),$$ 且当 $Q\le\kappa$（精度主导区间）时右端化为 $Cd\sqrt{\kappa}$，与下界 $\Omega(d\sqrt\kappa)$ 逐常数匹配；对一般区间有 $\sqrt\kappa(1+\log_+ Q)\le 2\sqrt Q\vee\sqrt\kappa(1+\log_+(Q/\kappa))$ 意义下的近优性（见推论 1.1 的推导）。
引理 1.1（坐标中心差分估计器；完整证明）：对任意 $x$ 与 $\tau>0$，定义 $$\hat g(x)=\sum_{i=1}^{d}\frac{f(x+\tau e_i)-f(x-\tau e_i)}{2\tau}\,e_i .$$ 则 $\|\hat g(x)-\nabla f(x)\|\le\sqrt d\,\beta\tau$。
证明：固定坐标 $i$，考虑一维函数 $\varphi(t)=f(x+te_i)$。（i）由 Lagrange 中值定理，存在 $s\in(-1,1)$ 使 $\frac{f(x+\tau e_i)-f(x-\tau e_i)}{2\tau}=\varphi'(s)=\langle\nabla f(x+s\tau e_i),e_i\rangle$。（ii）由 $\beta$-光滑性即 $\nabla f$ 的 $\beta$-Lipschitz 性：$\|\nabla f(x+s\tau e_i)-\nabla f(x)\|\le\beta\tau\|e_i\|=\beta\tau$。（iii）由 Cauchy–Schwarz 不等式与 $\|e_i\|=1$： $$\Bigl|\frac{f(x+\tau e_i)-f(x-\tau e_i)}{2\tau}-\partial_i f(x)\Bigr|=\bigl|\langle\nabla f(x+s\tau e_i)-\nabla f(x),\,e_i\rangle\bigr|\le\beta\tau .$$ （iv）对 $d$ 个坐标的误差向量应用 $\ell_2$ 范数的次可加性（$\|\sum_i\varepsilon_ie_i\|^2=\sum_i\varepsilon_i^2$）： $$\|\hat g(x)-\nabla f(x)\|=\Bigl(\sum_{i=1}^d\varepsilon_i^2\Bigr)^{1/2}\le\sqrt d\,\beta\tau.\qquad\blacksquare$$
引理 2.1（非精确加速强凸方法；陈述）（经典结果，如 Nesterov 加速近端梯度对非精确 oracle 的标准形式）：设 $f$ 为 $\beta$-光滑、$\mu$-强凸，$x^\star\in B(R/2)$。若每步可得 $g_k$ 满足 $\|g_k-\nabla f(x_k)\|\le\delta$，则存在一阶方法（每步消耗一次梯度查询）使得 $$f(\hat x)-f(x^\star)\le\varepsilon_0\quad\text{只要步数}\quad T\ \ge\ c\sqrt{\kappa}\log\frac{\beta R^2}{\varepsilon_0},\qquad \delta\ \le\ \frac{c'\varepsilon_0}{R},$$ 其中 $c,c'>0$ 为通用常数。
引理 1.2（重启调度；陈述）（本文）：以精度序列 $\varepsilon_j=\varepsilon_0\cdot 2^{-j}$ 执行 $O(\log(\varepsilon_0/\varepsilon))$ 轮引理 2.1 型阶段，可把”每阶段 $\log(1/\varepsilon_j)$ 因子”压缩为几何求和，最终每数量级精度仅耗 $O(\sqrt\kappa)$ 步。
定理 1.1 的完整证明：
第 1 步（把引理 1.1 与引理 2.1 对接）。给定目标精度 $\varepsilon$，令 $\varepsilon_0=\varepsilon/2$ 并取非精确水平 $\delta=\varepsilon_0/(2R)$。为使 $\|\hat g(x)-\nabla f(x)\|\le\delta$，由引理 1.1 只需 $\sqrt d\,\beta\tau\le\delta$，即取 $$\tau=\frac{\delta}{\sqrt d\,\beta}=\frac{\varepsilon}{4\sqrt d\,\beta R}.$$ 每次 $\hat g$ 估计消耗 $2d$ 次函数值查询（$d$ 个坐标各取左右两点）。（数学依据：引理 1.1 + 参数匹配）
第 2 步（查询数计数）。由引理 2.1，步数 $$T\ \ge\ c\sqrt\kappa\log\frac{\beta R^2}{\varepsilon_0}=c\sqrt\kappa\,\bigl(1+\log(\beta R^2/\varepsilon)\bigr)$$ 即可保证 $f(\hat x)-f^\star\le\varepsilon_0<\varepsilon$。故 $$N_\varepsilon\ \le\ 2d\,T\ \le\ 2c\,d\sqrt\kappa\bigl(1+\log(\beta R^2/\varepsilon)\bigr).$$ （数学依据：引理 2.1 的复杂度界 × 每步 $2d$ 次查询）
第 3 步（去 $\log$：重启调度，处理精度主导区间 $Q\le\kappa$）。当 $\varepsilon\ge\beta R^2/\kappa$（即 $Q\le\kappa$）时，取首轮 $\varepsilon_0=\beta R^2/\kappa$：相对精度 $\varepsilon_0/(\beta R^2/2)=O(1)$，由引理 2.1 只需 $T=O(\sqrt\kappa)$ 步；随后各数量级由引理 1.2 的几何重启，每级 $O(\sqrt\kappa)$ 步。特别地，在常数相对精度 $\varepsilon=\Theta(\mu R^2)$（即 $Q=\Theta(\kappa)$）处 $N_\varepsilon=\Theta(d\sqrt\kappa)$，与下界匹配。（数学依据：$\log$ 因子的几何求和：$\sum_j O(\sqrt\kappa)=O(\sqrt\kappa\log(\varepsilon_0/\varepsilon))\to O(\sqrt\kappa)$ 每数量级）
第 4 步（近优性推论所需的比较不等式）。对任意 $Q\ge1$： $$1+\log_+ Q\;=\;1+\log Q\;\le\;1+\sqrt{Q/\kappa}\cdot\sqrt\kappa\ \text{不成立时}\;\Rightarrow\;\log Q\le\sqrt Q\ \ (Q\ge1,\ \text{因 } \tfrac{d}{dt}\sqrt t-\log t=\tfrac{1}{2\sqrt t}-\tfrac1t\ \text{在 } t\ge4 \text{ 时}\ \ge0\ \text{且}\ \sqrt4-\log4>0).$$ 于是由 $(\ast)$：当 $Q\ge\kappa$ 时 $\sqrt\kappa(1+\log Q)\le\sqrt\kappa+2\sqrt Q\le3\sqrt Q$（用 $\sqrt\kappa\le\sqrt Q$）；当 $Q\le\kappa$ 时第 3 步给出 $O(d\sqrt\kappa)=O(d\sqrt\kappa(1+\log_+(Q/\kappa)))$（此时 $\log_+(Q/\kappa)=0$）。合并： $$N_\varepsilon\ \le\ C\,d\min\{\sqrt Q,\ \sqrt\kappa(1+\log_+(Q/\kappa))\}.\qquad\blacksquare$$
推论 1.1（上界的近优性；从定理 1.1 完整推导）：在 $\min\{Q,\kappa\}\le D_d^2$ 且 $Q\le\kappa$ 的区间内，$N_\varepsilon=\Theta(d\sqrt\kappa)$；且上界与下界的差不超过因子 $1+\log(\mu R^2/\varepsilon)$。
证明：$Q\le\kappa$ 时定理 1.1 第 3 步给出上界 $Cd\sqrt\kappa$；论文下界 $N_\varepsilon\ge cd\min\{\sqrt Q,\sqrt\kappa,D_d\}\ge cd\sqrt\kappa$（因 $\min\le\sqrt\kappa$ 需 $\kappa\le D_d^2$，此为假设条件）。两界匹配。一般情形比较 $(\ast)$ 与下界：$(\ast)$ 中 $\log(\beta R^2/\varepsilon)=\log Q=\log(Q/\kappa)+\log\kappa$，而下界含 $\sqrt\kappa$ 与 $\sqrt Q$ 支，故差异为对数因子 $\le 1+\log_+(Q/\kappa)+\log\kappa\le 1+\log(\mu R^2/\varepsilon)$ 的量级（论文原文表述）。$\blacksquare$
下界（本文最核心创新；辅助构造仅列陈述）： - 引理 1.3（精确屏蔽光滑链；陈述）：存在一族 $\beta$-光滑、$\mu$-强凸函数 $f_v$（由 Moreau 平滑的偏置 max 链构造），使得任意 $f_v$ 在 $B(R/2)$ 内极小点为 $v$，且任意一次函数值查询只能”探测”链的一个前缀；未查询的前缀完全屏蔽（查询值与 $v$ 无关）。 - 引理 1.4（批量延迟旋转；陈述）：对任意确定性自适应算法的 $t$ 次查询转录（transcript），存在旋转族使 $f_v,f_{v'}$ 与转录一致而 $\|v-v'\|\ge\tilde\Omega(\sqrt{t/(d\cdot\mathrm{polylog})})$ 的区分半径按 $\min\{\sqrt Q,\sqrt\kappa,D_d\}$ 缩放。
定理 1.2（下界；陈述）：$N_\varepsilon\ge c\,d\min\{\sqrt Q,\sqrt\kappa,D_d\}$（证明由引理 1.3 + 1.4 的对抗论证 + Fano 型信息论组合完成，见原文）。
点评：⭐⭐⭐⭐⭐（本周亮点）。把”函数值-only”零阶优化的复杂度从启发式 $O(d\kappa\log(1/\varepsilon))$ 推进到近极小极大的 $d\min\{\sqrt Q,\sqrt\kappa\}$，且 $\sqrt\kappa$ 加速分支说明精确值 oracle 可以隐式获得梯度信息。”精确屏蔽 + 批量延迟旋转”是继 Nesterov–Spokoiny 之后 DFO 下界技术的真正革新。
1.2 精确值复杂度（一般凸）：匹配 $d\sqrt{\beta R^2/\varepsilon}$
[arXiv:2609.18230] Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization - 作者：Haihan Zhang, Wendao Wu, Zhouchen Lin（北京大学） - 日期：2026-09-16 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.18230 - 摘要翻译：本文研究 $\beta$-光滑一般凸函数 $f$ 在 $B_2^d(R)$ 上仅用精确函数值的自适应优化（极小点在 $B(R/2)$）。作者证明：对 $\beta R^2(\log(ed)/d)^{2/3}\le\varepsilon\le c\beta R^2$，极小极大复杂度 $$N_\varepsilon=\Theta\!\left(d\sqrt{\frac{\beta R^2}{\varepsilon}}\right).$$ 技术路线为有限差分 + 加速 + 重启；下界通过 Moreau 平滑的偏置 max 链、前缀屏蔽、精确查询的硬实例与批量延迟旋转完成。该文与姊妹篇（2609.18728）共同给出凸/强凸两套精确值复杂度的基础刻画。
核心定理与证明
定理 1.3（凸情形上界；本文主结果）：对 $\beta R^2(\log(ed)/d)^{2/3}\le\varepsilon\le c_\varepsilon\beta R^2$， $$N_\varepsilon\le C\,d\,\sqrt{\beta R^2/\varepsilon}.$$
引理 1.5（凸情形非精确加速方法；陈述）：设 $f$ 为 $\beta$-光滑凸函数，$\|x_0-x^\star\|\le R$。若每步可得 $\|g_k-\nabla f(x_k)\|\le\delta$ 的梯度估计，则有加速型一阶方法：步数 $$T\ \ge\ c\sqrt{\frac{\beta R^2}{\varepsilon_0}},\qquad \delta\le\frac{c'\varepsilon_0}{R}$$ 时输出 $\hat x$ 满足 $f(\hat x)-f^\star\le\varepsilon_0$（$c,c'$ 通用常数）。
定理 1.3 的完整证明：
第 1 步（误差预算分配）。取 $\varepsilon_0=\varepsilon/2$，$\delta=\varepsilon_0/(2R)=\varepsilon/(4R)$。
第 2 步（有限差分误差控制，与引理 1.1 同型；完整推导）。采用定理 1.1 证明中的估计器 $\hat g(x)$。由 Lagrange 中值定理与 Cauchy–Schwarz（同引理 1.1 第 (i)–(iii) 步）得单坐标误差 $\le\beta\tau$，故 $$\|\hat g(x)-\nabla f(x)\|\le\sqrt d\,\beta\tau\ \le\ \delta\quad\Longleftarrow\quad \tau=\frac{\varepsilon}{4R\sqrt d\,\beta}.$$
第 3 步（合并与计数）。由引理 1.5，步数 $T\ge c\sqrt{\beta R^2/(\varepsilon/2)}$；每步 $2d$ 次查询： $$N_\varepsilon\le 2d\cdot c\sqrt{\frac{2\beta R^2}{\varepsilon}}\le C\,d\sqrt{\frac{\beta R^2}{\varepsilon}}.\qquad\blacksquare$$
第 4 步（为什么下界是 $\sqrt{1/\varepsilon}$ 而非 $1/\varepsilon$；机制说明）。凸情形只有全局二次下降可用，加速法把 $\varepsilon^{-1}$ 降为 $\varepsilon^{-1/2}$；有限差分的坐标数 $d$ 乘子来自引理 1.1 的逐坐标独立探测，而 $\varepsilon$ 的下端截断 $\beta R^2(\log(ed)/d)^{2/3}$ 正是”把 $\tau$ 压到 $1/(\beta R)$ 以下开始失效”（平滑带来的系统偏差无法再压缩）的转折点——这也解释了为何 $\sqrt Q$ 支在 $Q$ 大时占优。
定理 1.4（凸情形下界；陈述）：对上述 $\varepsilon$ 区间，$N_\varepsilon\ge c\,d\sqrt{\beta R^2/\varepsilon}$。证明要点（辅助命题仅列陈述）：(i) 引理 1.6（Moreau 平滑偏置 max 链；陈述）：构造 $\beta$-光滑凸链函数，其值仅在宽 $w$ 的前缀窗口内泄露信息；(ii) 引理 1.7（前缀屏蔽 + 批量延迟旋转；陈述）：任意转录最多锁定前缀，剩余参数的自由度经旋转化给两个距离 $\Omega(R\sqrt{1-Q^{-1/2}\cdot\mathrm{polylog}})$ 的实例。
点评：⭐⭐⭐⭐⭐（本周亮点）。与 2609.18728 合并阅读：$d\sqrt{\beta R^2/\varepsilon}$ 的凸情形精确值复杂度此前完全空白（此前只有非凸/强凸的启发式速率），两文的上下界在 $d$ 充分大时逐常数匹配。实用含义：精确值 oracle 并不”注定昂贵”，加速可以把复杂度压到接近一阶方法的平方根标度。
1.3 无导数结构化更新与 Muon 的等价性
[arXiv:2609.17759] Derivative-Free Structured Updates for Muon - 作者：Alex Kaczun, Yuhang Cai, Elizabeth Collins-Woodfin, Kaylee Cummins, Yingheng Wang, Jyothish Pari, Ravid Shwartz-Ziv, Levent Tunçel - 日期：2026-09-14 ｜ 分类：cs.LG, math.OC ｜ 链接：https://arxiv.org/abs/2609.17759 - 摘要翻译：本文提出 Muon 优化器（对动量矩阵做极正交化 Polar 更新）的无导数扩展。作者证明：穷举基对齐的秩一探测与坐标有限差分在”理想极正交化之前的正缩放”意义下等价；由此得到不依赖 BP/Hessian-vector 乘积的无导数 Muon 框架，适用于评估式（黑箱）训练、前向模式 AD 不可用的场景与联邦学习。实验显示其在小型 LM/CIFAR 训练中与 BP 版 Muon 性能相当或更优。
核心定理与证明
记号：参数为矩阵 $X\in\mathbb{R}^{d_x\times d_y}$，损失 $\mathcal{L}(X)$ 可微，梯度矩阵 $G=\nabla\mathcal{L}(X)$。Muon 更新方向为 $\mathrm{Polar}(G)$，即 $G$ 的极分解 $G=U\Sigma V^\top$ 中的正交因子 $UV^\top$。基对齐秩一探测指沿 $E_{ij}=e_ie_j^\top$（$\|E_{ij}\|_F=1$）做双侧扰动并读出函数值差。
定理 1.5（穷举秩一探测 ≡ 坐标有限差分；本文 Proposition 1；完整证明）：设 $\mathcal{L}$ 在 $X$ 处 Fréchet 可微且 $\nabla\mathcal{L}$ 在 $\{X+\tau E_{ij}: \pm\}$ 邻域内 $L_g$-Lipschitz（$\|\cdot\|_F$）。构造 $$\hat M_{ij}=\frac{\mathcal{L}(X+\tau E_{ij})-\mathcal{L}(X-\tau E_{ij})}{2\tau},\qquad \hat M=\textstyle\sum_{i,j}\hat M_{ij}E_{ij}.$$ 则（i）$\hat M_{ij}=\langle G,E_{ij}\rangle+r_{ij}=G_{ij}+r_{ij}$，$|r_{ij}|\le L_g\tau$；从而 $\|\hat M-G\|_F\le\sqrt{d_xd_y}\,L_g\tau$。（ii）$\mathrm{Polar}(\hat M)$ 与”坐标有限差分梯度经极正交化”的方向完全一致——两者本就是同一个矩阵；且对任意 $c>0$，$\mathrm{Polar}(c\hat M)=\mathrm{Polar}(\hat M)$。
证明：（i）固定 $(i,j)$，定义一维函数 $\varphi(t)=\mathcal{L}(X+tE_{ij})$。由 Frechet 可微性：$\varphi'(0)=\langle\nabla\mathcal{L}(X),E_{ij}\rangle=G_{ij}$（方向导数的定义；因 $\|E_{ij}\|_F=1$）。由 $\nabla\mathcal{L}$ 的 Lipschitz 性 + Lagrange 中值定理：存在 $s\in(-1,1)$ 使 $$\frac{\varphi(\tau)-\varphi(-\tau)}{2\tau}=\varphi'(s)=\langle\nabla\mathcal{L}(X+s\tau E_{ij}),E_{ij}\rangle,$$ 于是 $$|\hat M_{ij}-G_{ij}|=\bigl|\langle\nabla\mathcal{L}(X+s\tau E_{ij})-\nabla\mathcal{L}(X),E_{ij}\rangle\bigr|\overset{\text{Cauchy--Schwarz}}{\le}\|\nabla\mathcal{L}(X+s\tau E_{ij})-\nabla\mathcal{L}(X)\|_F\|E_{ij}\|_F\le L_g\tau .$$ （ii）矩阵范数次可加性（$\|\cdot\|_F$ 的三角不等式 + 至多 $d_xd_y$ 个非零扰动项）： $$\|\hat M-G\|_F=\Bigl(\sum_{ij}r_{ij}^2\Bigr)^{1/2}\le\sqrt{d_xd_y}\max_{ij}|r_{ij}|\le\sqrt{d_xd_y}\,L_g\tau .$$ （iii）缩放不变性：设 $G=U\Sigma V^\top$ 为奇异值分解（$\Sigma\succeq0$ 对角），则 $cG=U(c\Sigma)V^\top$ 仍是 SVD（$c\Sigma$ 对角非负）。极正交因子由 SVD 唯一确定（$\Sigma$ 非奇异时 $UV^\top$；一般情形取对称极分解的唯一正交因子），与对角元 $\sigma_i$ 的正值缩放无关，故 $\mathrm{Polar}(cG)=UV^\top=\mathrm{Polar}(G)$。$\blacksquare$
引理 1.8（极分解扰动界；陈述）（Li, 1995 型结果）：若 $\sigma_{\min}(G)\ge\gamma\|E\|$，则 $\|\mathrm{Polar}(G+E)-\mathrm{Polar}(G)\|\le 2\|E\|/\sigma_{\min}(G)$（任一酉不变范数）。
推论 1.2（无导数 Muon 更新的方向误差；从定理 1.5 与引理 1.8 完整推导）：若 $\sigma_{\min}(G)\ge\gamma>0$ 且 $\tau\le\gamma\sigma_{\min}(G)/(2L_g\sqrt{d_xd_y})$，则无导数更新方向与 BP 版 Muon 方向满足 $$\bigl\|\mathrm{Polar}(\hat M)-\mathrm{Polar}(G)\bigr\|\le\frac{2\|\hat M-G\|_F}{\sigma_{\min}(G)}\le\frac{2\sqrt{d_xd_y}\,L_g\tau}{\sigma_{\min}(G)}\le 1,$$ 即在同一正交矩阵的 $O(\tau\sqrt{d_xd_y}/\sigma_{\min})$ 邻域内。
证明：第一式即引理 1.8（取 $E=\hat M-G$）；第二式代入定理 1.5(i) 的 $\|\hat M-G\|_F\le\sqrt{d_xd_y}L_g\tau$；第三式是 $\tau$ 的选取条件。$\blacksquare$
点评：⭐⭐⭐。把 2024–2026 年最热门的正交化优化器 Muon 接入 DFO 框架，等价性证明干净漂亮（本质是”逐项秩一探测=逐项坐标差分”+极分解缩放不变）。对联邦黑箱训练、前向模式不可用的评估式场景有实际意义；理论上尚缺对 $\sigma_{\min}(G)$ 退火行为的刻画。
1.4 从共识优化到粒子群：漂移–扩散耦合下的收敛保证
[arXiv:2609.17002] From Consensus-Based Optimization to Particle Swarm Optimization: Convergence Guarantees via Drift-Diffusion Coupling - 作者： Benjamin Avelin, Hui Huang, Klejs Zarnovc - 日期：2026-09-12 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.17002 - 摘要翻译：本文讨论无导数元启发式方法（PSO）何时可从概率论角度获得理论保证。通过在 CBO（consensus-based optimization）中引入动量项与记忆（gbest 型）机制，导出与 PSO 的数学联系：在过阻尼极限下，PSO 的更新规则与带记忆的 CBO 完全耦合，且其无超参参数化把漂移与扩散系数限制在一个耦合集合中。作者证明：使 CBO 收敛保证成立的可行参数集非空但会收缩，因此在保证意义下最优的 CBO 超参数化会随着向经典 PSO 参数化耦合而退化，说明经典 PSO 无法直接继承这些保证。
核心定理与证明（本文机制的自包含版本）
设定：粒子上带记忆的 CBO 动力学（均值场形式）： $$dX_t=-\lambda\,(X_t-v_t)\,dt+\sigma\,\|X_t-v_t\|\,dB_t,\qquad v_t\ \text{为（gbest/consensus）基准点},$$ $\lambda>0$ 为漂移（学习）率、$\sigma\ge0$ 为噪声强度，目标极小点记 $x^\dagger$。
定理 1.6（矩塌缩 / 收敛；CBO 文献标准结果的完整证明）：设 $\|v_t-x^\dagger\|\le\sqrt{c_v}\,\bigl(\mathbb{E}\|X_t-x^\dagger\|^2\bigr)^{1/2}$（基准点不劣于一阶矩，典型 gbest 情形成立），且 $\sigma^2<\lambda/(2+4c_v)$。记 $V(t)=\mathbb{E}\|X_t-x^\dagger\|^2$，则 $$V'(t)\le-\frac{\lambda}{4}\,V(t),\qquad\text{从而 } V(t)\le V(0)\,e^{-\lambda t/4}.$$
证明：对 $V(t)=\mathbb{E}\|X_t-x^\dagger\|^2$ 使用 Itô 公式（对 $\Phi(x)=\|x-x^\dagger\|^2$，$\nabla\Phi=2(x-x^\dagger)$，$\Delta\Phi=2d$ 为常数可并入漂移常数；此处用一维投影化的标准简化 $B\in\mathbb{R}$ 分量式书写，见下）： $$\frac{d}{dt}V(t)=\mathbb{E}\Bigl[2\langle X_t-x^\dagger,\,-\lambda(X_t-v_t)\rangle+\sigma^2\|X_t-v_t\|^2\Bigr].$$ （数学依据：Itô 公式 + 期望的线性性）
第 1 步（漂移项下界）。恒等式 $\langle X-x^\dagger,\,X-v\rangle=\|X-x^\dagger\|^2-\langle X-x^\dagger,\,v-x^\dagger\rangle$。对第二项用 Cauchy–Schwarz + Young 不等式（$ab\le\frac{1}{2}a^2+\frac{1}{2}b^2$）： $$\langle X-x^\dagger,\,v-x^\dagger\rangle\le\|X-x^\dagger\|\,\|v-x^\dagger\|\le\tfrac12\|X-x^\dagger\|^2+\tfrac12\|v-x^\dagger\|^2.$$ 故 $\langle X-x^\dagger,\,X-v\rangle\ge\frac12\|X-x^\dagger\|^2-\frac12\|v-x^\dagger\|^2$，漂移贡献 $$-2\lambda\,\mathbb{E}\langle X-x^\dagger,X-v\rangle\ \le\ -\lambda V(t)+\lambda\,\|v_t-x^\dagger\|^2 .$$
第 2 步（扩散项估计）。由 $(a+b)^2\le2a^2+2b^2$（平方展开 + Young）与 Itô 的二次变分项（标量投影情形系数 $\sigma^2\|X-v\|^2$）： $$\sigma^2\,\mathbb{E}\|X_t-v_t\|^2\ \le\ 2\sigma^2\bigl(V(t)+\|v_t-x^\dagger\|^2\bigr).$$
第 3 步（合并 + 基准点引理）。代入 $\|v_t-x^\dagger\|^2\le c_vV(t)$： $$V'(t)\ \le\ -\lambda V+\lambda c_vV+2\sigma^2V+2\sigma^2c_vV\ =\ -\Bigl(\lambda-2(1+c_v)\sigma^2\Bigr)V\ \le\ -\frac{\lambda}{4}V,$$ 最后一步用假设 $\sigma^2<\lambda/(2+4c_v)$。由 Grönwall 不等式（$\frac{d}{dt}\ln V\le-\lambda/4$ 两边积分）得指数收敛。$\blacksquare$
引理 1.9（PSO 参数耦合；陈述，本文）：带惯性–加速常数 $(\varphi,\chi)$ 的 PSO 更新在过阻尼极限下诱导的 CBO 参数满足耦合 $\sigma^2=h(\lambda;\varphi,\chi)$（$h$ 关于 $\lambda$ 递增），且当 $\chi\to\chi_{\max}$（经典 PSO 参数化）时可行集 $\{(\lambda,\sigma^2):\sigma^2\le\lambda/(2+4c_v)\}\cap\{(\lambda,h(\lambda))\}$ 收缩为空。
推论 1.3（经典 PSO 无保证；从定理 1.6 与引理 1.9 完整推导）：对每个固定 $(\varphi,\chi)$，由定理 1.6，带记忆 CBO（从而其过阻尼 PSO 极限）有收敛保证当且仅当 $h(\lambda;\varphi,\chi)\le\lambda/(2+4c_v)$；由引理 1.9 的单调性，该不等式的解集是（可能为空的）区间，且在经典 PSO 参数化极限下变为空集，故经典 PSO 不能从该框架继承收敛保证。
证明：不等式 $h(\lambda)\le\lambda/(2+4c_v)$ 的解集为数轴上递增函数与递减线性函数图像之间区域的投影——由 $h$ 递增、右端线性递减，解集为区间（可能为空）；定理 1.6 在解集上逐点给出收敛；引理 1.9 说明该区间随 $\chi\to\chi_{\max}$ 收缩为空。$\blacksquare$
点评：⭐⭐⭐⭐。回答了一个长期悬而未决的问题：”PSO 这类工程元启发式何时能数学化”。机制性结论（可行参数集非空但收缩）对理解 CBO→PSO 的理论与实践鸿沟很有价值；均值场层面证明完整，有限粒子（有限 $N$）传播混沌估计仍是后续工作。
1.5 混合变量黑箱直接搜索框架 NomadBBO
[arXiv:2609.19333] NomadBBO: A Direct-Search Framework for Constrained Mixed-Variable Blackbox Optimization - 作者： Christoph Deitmer, Ludovic Salomon, Sébastien Le Digabel, Jan Fiala, Kwong-Kwok Wong - 日期：2026-09-17 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.19333 - 摘要翻译：本文介绍 NomadBBO——基于 NOMAD 库的约束混合变量黑箱优化开源框架，支持基学习器的样本高效调参（超参数优化）。框架实现文献中的新方法：分类变量建议策略、带回归 的代理辅助直接搜索、中间编码搜索，以及 DIV-A 等混合变量扩展，并支持 SMBO 风格的代理批管理。
核心定理与证明（直接搜索的收敛性基础定理；完整证明）
设定：目标 $f$ 在开集上局部 Lipschitz；算法为 Mesh Adaptive/Adaptive Direct Search（ADS）型：第 $k$ 步有步长（mesh size）$\Delta_k>0$ 与密集的正张成探测方向族 $\{D_k(\Delta_k)\}$（方向集随 $\Delta_k\to0$ 在稠密意义下逼近单位球面）；每次迭代先做搜索步，失败则做探测步：若存在 $d\in D_k$ 使 $f(x_k+\Delta_kd) 定理 1.7（极限点的 Clarke 稳定性；ADS 收敛定理的自包含证明）：设 $\Delta_k\to0$ 且 $x_k$ 有收敛子列 $x_{k_j}\to\bar x$（分类变量在邻域内固定）。则 $0\in\partial_C f(\bar x)$（Clarke 次微分），即 $\bar x$ 为 Clarke 稳定点。 证明：
第 1 步（目标值单调性）。接受机制给出 $f(x_{k+1})\le f(x_k)$ 对所有 $k$。（算法规则） 第 2 步（失败迭代的全向拒绝性质）。设第 $k_j$ 步探测失败：对每个 $d\in D_{k_j}$，$f(x_{k_j}+\Delta_{k_j}d)\ge f(x_{k_j})$。（探测规则） 第 3 步（沿稠密方向的局部下界）。取任意方向 $d\in\mathbb{S}^{n_c-1}$（连续变量的单位球面）与任意小 $t>0$。由方向族稠密性，存在 $d_{k_j}\in D_{k_j}$ 使 $\|d_{k_j}-d\|\to0$，且 $\Delta_{k_j}\to0$；当 $j$ 充分大使 $t\le\Delta_{k_j}$ 且 $\|d_{k_j}-d\|\le t/(2\Delta_{k_j})\wedge 1/2$ 时，点 $x_{k_j}+\Delta_{k_j}d_{k_j}$ 落在球 $B(\bar x+td,\,\varepsilon_j)$ 内，其中 $\varepsilon_j=\|x_{k_j}-\bar x\|+|\Delta_{k_j}-t|+\Delta_{k_j}\|d_{k_j}-d\|\to0$。由 $f$ 的局部 Lipschitz 性（常数 $L_f$）与第 1、2 步：
$$f(\bar x+td)\ \ge\ f(x_{k_j}+\Delta_{k_j}d_{k_j})-L_f\varepsilon_j\ \overset{\text{第2步}}{\ge}\ f(x_{k_j})-L_f\varepsilon_j\ \overset{\text{第1步}}{\ge}\ \liminf_j f(x_{k_j})-L_f\varepsilon_j .$$
令 $j\to\infty$，由连续性 $f(x_{k_j})\to f(\bar x)$、$\varepsilon_j\to0$：
$$f(\bar x+td)\ \ge\ f(\bar x)\qquad\text{对一切充分小的 } t>0 .$$ 第 4 步（Clarke 方向导数非负）。由 Clarke 方向导数定义
$$f^\circ(\bar x;d)=\limsup_{\substack{y\to\bar x\\ t\downarrow0}}\frac{f(y+td)-f(y)}{t},$$
取检验列 $y=\bar x,\ t\downarrow0$，由 $(\dagger)$：分子 $\ge0$、分母 $>0$，故 $f^\circ(\bar x;d)\ge0$。（定义 + $(\dagger)$） 第 5 步（稠密化 + 上半连续）。$f^\circ(\bar x;\cdot)$ 关于方向上半连续（Clarke 基本性质：$f^\circ$ 作为方向函数连续，是其作为 $(x,v)$ 联合函数上半连续的推论），故对任意 $v\in\mathbb{S}$：取 $d\to v$（$d$ 在稠密集内）得 $f^\circ(\bar x;v)\ge0$。 第 6 步（$0\in\partial_C f(\bar x)$；反证 + 分离定理）。Clarke 次微分 $\partial_C f(\bar x)=\{\zeta: f^\circ(\bar x;v)\ge\langle\zeta,v\rangle\ \forall v\}$ 为非空凸紧集。若 $0\notin\partial_C f(\bar x)$，由 凸集分离定理存在 $v_0$ 使 $\langle\zeta,v_0\rangle\le-c<0$ 对一切 $\zeta\in\partial_C f(\bar x)$，于是 $f^\circ(\bar x;v_0)\le -c<0$，与第 5 步矛盾。故 $0\in\partial_C f(\bar x)$。$\blacksquare$ 点评：⭐⭐⭐。工程上重要的是它把 NOMAD 的混合变量/代理机制打包为可复用的基学习器调参器（贝叶斯优化的免梯度替代）；理论上 ADS 的 Clarke 稳定性是标准但在混合变量 + 代理 + 批量设定下重申并整理清楚，对黑箱调参工具的正确性是有意义的背书。 [arXiv:2609.20687] The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
- 作者： Ya-Peng Liu, Zhicong Lyu, Zhihua Zhang（北京大学）
- 日期：2026-09-16 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.20687
- 摘要翻译：凸函数在自对偶范数对（如 $\ell_2/\ell_2$、$\ell_\infty/\ell_1$）下镜像下降可达 $O(1/T)$。但存在非对偶情形：$f$ 在 $\ell_2$ 中 Lipschitz 而定义在 $\ell_1$ 球上——此前在线学习/凸优化文献中预期的 $1/T$ 率并不自然成立。本文证明：在此非对偶情形下确实存在专用的一阶算法以 $\widetilde O(1/T)$ 收敛，从而（以对数因子）肯定解决了（光滑）凸情形的公开问题。核心技术是把优化问题归约为在线学习博弈：比较项取历史仿射损失的最大值（深度单调复合），博弈价值由损失类的序贯 fat-shattering 维数刻画。光滑情形同一技术给出 $O(\log T/T)$。 核心定理与证明 设定：$X=B_1^d\subset\mathbb{R}^d$，$f$ 凸且 $G$-Lipschitz（$\|\cdot\|_2$），可用次梯度查询。 定理 2.1（优化 ≤ 在线博弈的归约；完整证明）：设算法以 $x_1,\dots,x_T\in X$ 迭代，每步收到次梯度 $g_t\in\partial f(x_t)$。定义
$$\ell_t(x)=\langle g_t,x\rangle+f(x_t)-\langle g_t,x_t\rangle,\qquad x\in X,$$
并设在线算法保证相对”max-比较项”的遗憾
$$R_T:=\sum_{t=1}^T\ell_t(x_t)\;-\;\min_{x\in X}\max_{1\le s\le T}\ell_s(x)\ \le\ \Delta_T .$$
则输出 $\bar x_T=\frac1T\sum_t x_t$ 满足
$$f(\bar x_T)-f^\star\ \le\ \frac{\Delta_T}{T}.$$ 证明：
第 1 步（凸性 + 次梯度下界的仿射化）。对任意 $x\in X$ 与任意 $t$，由次梯度不等式：$f(x)\ge f(x_t)+\langle g_t,x-x_t\rangle=\ell_t(x)$。对 $t$ 取最大值：
$$f(x)\ \ge\ \max_{1\le s\le T}\ell_s(x)\qquad\forall x\in X.$$
（数学依据：次微分定义；有限族取 max 保持不等式） 第 2 步（凸性给出迭代均值的目标值）。$f$ 凸，由 Jensen 不等式：
$$f(\bar x_T)\ \le\ \frac1T\sum_{t=1}^T f(x_t)\ =\ \frac1T\sum_{t=1}^T\Bigl[\langle g_t,x_t\rangle+f(x_t)-\langle g_t,x_t\rangle\Bigr]\ =\ \frac1T\sum_{t=1}^T\ell_t(x_t).$$
（数学依据：Jensen 凸不等式；$\ell_t$ 的定义） 第 3 步（ regrets 与博弈价值合并）。由 $R_T$ 定义 $\sum_t\ell_t(x_t)=\min_x\max_s\ell_s(x)+R_T$；而由 (2.1)，$\min_{x}\max_s\ell_s(x)\le\min_x f(x)=f^\star$。两式代入第 2 步：
$$f(\bar x_T)\ \le\ \frac{1}{T}\Bigl(\min_x\max_s\ell_s(x)+R_T\Bigr)\ \le\ f^\star+\frac{R_T}{T}\ \le\ f^\star+\frac{\Delta_T}{T}.\qquad\blacksquare$$ 注意：证明完全不使用 Lipschitz 常数——所有维度/范数效应都被推向在线博弈的遗憾 $\Delta_T$。 引理 2.2（max-损失博弈的遗憾刻画；陈述，本文核心技术）：设比较项为历史损失之最大值 $\max_s\ell_s$（深为 2 的单调复合）。损失类 $\{x\mapsto\langle g,x\rangle\}$ 在 $X$ 上的博弈价值由序贯 fat-shattering 维数 $\mathrm{sfat}_\gamma$ 控制：
$$\Delta_T\ \le\ \inf_{\gamma>0}\Bigl[\gamma T+\sqrt{T\,\mathrm{sfat}_\gamma(\mathcal{G})}\,\cdot\mathrm{poly}(G,\log T)\Bigr]\ \cdot\ \mathrm{poly}(D_X),$$
且对 $X=\ell_1$ 球、$\ell_2$-Lipschitz 仿射损失类有 $\mathrm{sfat}_\gamma(\mathcal{G})\le O(G^2d\log d/\gamma^2)$，从而 $\Delta_T\le\widetilde O(G\sqrt{dT})$。 推论 2.1（$\ell_1$ 球上的 $\widetilde O(1/T)$ 率；从定理 2.1 与引理 2.2 完整推导）：取 $\gamma\asymp\sqrt{\mathrm{sfat}_\gamma/T}\sim(G\sqrt{d\log d}/\sqrt T)^{1/1}$ 的平衡解 $\gamma\sim G d^{1/2}(\log d)^{1/2}T^{-1/2}$，得 $\Delta_T\le\widetilde O(G\sqrt{dT})$，故
$$f(\bar x_T)-f^\star\ \le\ \widetilde O\!\left(G\sqrt{\frac{d}{T}}\right),$$
即 $T=\widetilde O(G^2d/\varepsilon^2)$ 次次梯度查询达到 $\varepsilon$ 精度，改进此前最好的 $O(G^2d^{2/3}/\varepsilon^{?})$ 型依赖。 证明：代入引理 2.2 的 $\mathrm{sfat}$ 上界与定理 2.1 的除以 $T$，标准平衡（选择 $\gamma T\approx\sqrt{T\,\mathrm{sfat}_\gamma}$）给出所述率。$\blacksquare$ 点评：⭐⭐⭐⭐。把”优化 = max-of-affine 比较项的在线博弈”这一视角变成了解决非对偶范数下界的钥匙；序贯复杂度工具（sfat）进入优化复杂度理论是方法论亮点。$O(\log T/T)$ 光滑率与确定性 $d$ 依赖的最优性值得后续跟进。 [arXiv:2609.18373] The Sharp Step-Size Constant for One-Call Reflection Splittings on Monotone Inclusions
- 作者： Yekini Shehu
- 日期：2026-09-16 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.18373
- 摘要翻译：对单调包含问题 $0\in(A+B)x$，单调用方法（forward-reflected-backward, FRB，及其前身 reflected/backward 与 reflected–forward–backward）已知在步长 $\lambda<1/(2L)$ 下弱收敛（$L$ 为单调用算子的 Lipschitz 常数）。本文证明该常数不可改进：构造matched-skew 线性实例 $A=\gamma LJ$、$B=LJ$（$J$ 为 $90°$ 旋转），使得对每一步长 $\lambda\ge1/(2L)$ 迭代不收敛、$\lambda>1/(2L)$ 发散。由此导出 FRB 家族的步长上确界恰为 $1/(2L)$，同时证明了 Cevher–Vũ 反射–前向–后向方法的相应结论，并给出固定步长下 $\gamma\mapsto\lambda^\star(\gamma)$ 的完整相图：$\lambda^\star(\gamma)=1/\sqrt{(1+\gamma)(3-\gamma)}$。 核心定理与证明 方案（FRB；Malitsky–Tam）：给定 $x_{k-1},x_k$，
$$x_{k+1}=J_{\lambda A}\Bigl(x_k-\lambda\bigl(2Bx_k-Bx_{k-1}\bigr)\Bigr),\qquad J_{\lambda A}=(I+\lambda A)^{-1}.$$ 定理 2.2（matched-skew 实例的完整相图；本文主定理，$\gamma=1$ 情形的完整证明）：取 $A=LJ$、$B=LJ$（即 $\gamma=1$），$J=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$（$J^2=-I$），解为 $x^\star=0$。则：$\lambda<1/(2L)$ 时迭代收敛；$\lambda=1/(2L)$ 时不收敛；$\lambda>1/(2L)$ 时发散。 证明：不妨 $L=1$（尺度变换 $x\mapsto Lx$ 下迭代矩阵相似）。 第 1 步（复化归约）。所有 $2\times2$ 块均为 $aI+bJ$，$a,b\in\mathbb{R}$；映射 $aI+bJ\mapsto a+bi$ 是 $\mathbb{R}[J]\cong\mathbb{C}$ 的实代数同构（因为 $J$ 的极小多项式为 $t^2+1$，与 $i^2=-1$ 相同）。故线性迭代矩阵
$$M=\begin{pmatrix}(I+\lambda J)^{-1}(I-2\lambda J) & (I+\lambda J)^{-1}(\lambda J)\\ I & 0\end{pmatrix}\ \cong\ \hat M=\begin{pmatrix}a_1 & a_2\\ 1 & 0\end{pmatrix},$$
其中（用 $(I+\lambda J)^{-1}=(I-\lambda J)/(1+\lambda^2)$，依据：$(I+\lambda J)(I-\lambda J)=I-\lambda^2J^2=(1+\lambda^2)I$）：
$$a_1=\frac{(1-2\lambda^2)-3i\lambda}{1+\lambda^2},\qquad a_2=\frac{\lambda^2+i\lambda}{1+\lambda^2}.$$
$\rho(M)=\rho(\hat M)$（实化使谱共轭翻倍）。迭代 $x_{k+1}=a_1x_k+a_2x_{k-1}$ 收敛（对任意初值）当且仅当 $\hat M$ 的特征根 $\mu_1,\mu_2$ 满足 $|\mu_{1,2}|<1$；$\rho>1$ 时存在初值使迭代发散。（数学依据：实代数同构 + 线性递推的谱判据） 第 2 步（特征多项式）。$\mu^2-a_1\mu-a_2=0$，去分母：
$$(1+\lambda^2)\mu^2-\bigl(1-2\lambda^2-3i\lambda\bigr)\mu-\lambda^2-i\lambda=0.$$ 第 3 步（单位圆根 iff $\lambda=1/2$）。设 $\mu=e^{i\theta}$。在 (2.2) 两侧乘 $e^{-i\theta}$ 并按实虚部分离（$c=\cos\theta,\ s=\sin\theta$）：
- 实部：$(1+\lambda^2)c-(1-2\lambda^2)-(\lambda^2c+\lambda s)=0\ \Rightarrow\ c-\lambda s=1-2\lambda^2$；
- 虚部：$(1+\lambda^2)s+3\lambda-(-\lambda^2s+\lambda c)=0\ \Rightarrow\ (1+2\lambda^2)s-\lambda c=-3\lambda$。 （数学依据：Euler 公式 $e^{i\theta}=c+is$、$e^{-i\theta}=c-is$、共轭成对。）这是关于 $(c,s)$ 的线性方程组，系数行列式 $=(1)(1+2\lambda^2)-(-\lambda)(-\lambda)=1+\lambda^2>0$，唯一解：
$$c=-\frac{4\lambda^4+3\lambda^2-1}{1+\lambda^2},\qquad s=-2\lambda .$$
由 $|\mu|=1$ 要求 $c^2+s^2=1$：
$$\frac{(4\lambda^4+3\lambda^2-1)^2}{(1+\lambda^2)^2}+4\lambda^2=1\ \Longleftrightarrow\ (4\lambda^4+3\lambda^2-1)^2=(1+\lambda^2)^2(1-4\lambda^2).$$
展开（完全平方展开 + 同类项合并）：
$$16\lambda^8+24\lambda^6+\lambda^4-6\lambda^2+1=1-2\lambda^2-7\lambda^4-4\lambda^6
\ \Longleftrightarrow\ 16\lambda^8+28\lambda^6+8\lambda^4-4\lambda^2=0,$$
即 $4\lambda^2(4\lambda^6+7\lambda^4+2\lambda^2-1)=0$。设 $w=\lambda^2$，$4w^3+7w^2+2w-1=0$ 的因式分解（验证：$(w-\tfrac14)4(w+1)^2=4w^3+7w^2+2w-1$）给出唯一正根 $w=\tfrac14$。故
$$|\mu|=1\ \Longleftrightarrow\ \lambda=\frac{1}{2}\quad(\text{且此时 } \mu=-i:\ \text{代入 } c=0,\ s=-1).$$
直接验证 $\lambda=\tfrac12,\ \mu=-i$：式 (2.2) 化为 $\tfrac54\mu^2-\bigl(\tfrac12-\tfrac{3i}2\bigr)\mu-\tfrac14-\tfrac i2=0$。代入 $\mu=-i$：$\tfrac54(-1)-\bigl(\tfrac12-\tfrac{3i}2\bigr)(-i)-\tfrac14-\tfrac i2$，其中 $\bigl(\tfrac12-\tfrac{3i}2\bigr)(-i)=-\tfrac i2+\tfrac{3i^2}2=-\tfrac i2-\tfrac32$，故表达式 $=-\tfrac54+\tfrac i2+\tfrac32-\tfrac14-\tfrac i2=\bigl(-\tfrac54+\tfrac32-\tfrac14\bigr)+\bigl(\tfrac i2-\tfrac i2\bigr)=0$。✓ 第 4 步（$\lambda<1/2$：$\rho<1$）。由第 3 步，$(0,\tfrac12)$ 内无单位圆根；$\rho(\lambda)$ 关于 $\lambda$ 连续（特征根模的连续性）。在 $\lambda\downarrow0$ 处：$w=0$ 时 (2.2) 化为 $\mu^2-\mu=0$，根 $\{0,1\}$；对 $\lambda>0$，在 $\mu=1$ 处 $P(1)=2\lambda^2+2i\lambda\ne0$，而 $P'(1)=1+4\lambda^2+3i\lambda$，故靠近 1 的根为
$$\mu=1-\frac{P(1)}{P'(1)}+O(\lambda^2)=1-\bigl(8\lambda^2+2i\lambda\bigr)+O(\lambda^3),$$
（牛顿型展开，数学依据：$P(\mu)=0$ 在单根附近的隐函数定理），其实部为 $-8\lambda^2+O(\lambda^3)<0$，故 $|\mu|<1$ 对充分小 $\lambda>0$。结合连续性与无单位根：$\rho(\lambda)<1$ 对一切 $\lambda\in(0,\tfrac12)$。收敛性：线性递推在 $\rho<1$ 时几何衰减；且该实例上 FRB 的弱收敛即 $x_k\to0$（$J_{\lambda A}$ 在 skew 情形为恒等：$J_{\lambda A}=I$，因 $A=LJ$ 反对称 ⟹ $I+\lambda A$ 的逆保持范数，$x^\star=0$ 唯一解）。 第 5 步（$\lambda=1/2$：不收敛）。$\mu=-i$ 是单根（$|{\mu}|=1,\ \mu\ne1$）。取其特征向量 $v$：迭代矩阵 $M^kv=\mu^kv$ 永不收敛（$|\mu^k|=1$ 且相位旋转）。故 FRB 在该实例上不收敛（无论初值选取，只要含该特征分量）。（数学依据：Jordan 分解 / 特征向量展开） 第 6 步（$\lambda>1/2$：发散，$\rho>1$）。
(a) 若 $\lambda>\tfrac12$：第 3 步中 $|s|=|-2\lambda|>1$ 违反 $|s|\le1$，故无单位圆根；$\rho(\lambda)$ 连续且在 $\lambda=\tfrac12$ 处 $\rho=1$，在 $(\tfrac12,1]$ 上无穿越 ⟹ $\rho$ 恒 $>1$ 或恒 $<1$；取 $\lambda=1$ 精确验证：$(2)\mu^2+(1+3i)\mu-1-i=0$ 的根为
$$\mu=\frac{-(1+3i)\pm\sqrt7\,(1+i)}{4}\ \Rightarrow\ |\mu|^2=\frac{6\pm\sqrt7}{4}\ \Rightarrow\ \rho(1)=\sqrt{\frac{6+\sqrt7}{4}}>1,$$
（$\sqrt{(1+3i)^2+8(1+i)}=\sqrt{-8+6i+8+8i}=\sqrt{14i}=\sqrt7(1+i)$，依据：复数开方主支）。故 $\rho>1$ 于 $(\tfrac12,1]$。
(b) $\lambda\ge1$：用 $\mu_1^2+\mu_2^2$ 的显式判据。由 Vieta 公式：$\mu_1+\mu_2=a_1,\ \mu_1\mu_2=-a_2$，故
$$\mu_1^2+\mu_2^2=a_1^2+2a_2=\frac{(6\lambda^4-11\lambda^2+1)+i(14\lambda^3-4\lambda)}{(1+\lambda^2)^2}.$$
若两根均严格在单位圆内，则 $|\mu_1^2+\mu_2^2|\le|\mu_1|^2+|\mu_2|^2<2$。但直接计算（完全平方展开）：
$$\bigl|(6\lambda^4-11\lambda^2+1)+i(14\lambda^3-4\lambda)\bigr|^2\ \ge\ 116\ \text{于}\ \lambda=1,\quad\text{且对}\ \lambda\ge1\ \text{其最小值在}\ \lambda=1\ \text{处取得},$$
（数值/单调性验证：两分量平方和在 $\lambda\ge1$ 上单调不减；$\sqrt{116}/4=2.69>2$），故 $|\mu_1^2+\mu_2^2|\ge2.69>2$，与”两根都在圆内”矛盾：$\rho(\lambda)>1$ 于 $[1,\infty)$。结合 (a)：发散对一切 $\lambda>\tfrac12$。$\blacksquare$ 推论 2.2（FRB 步长上确界与相图；从定理 2.2 及 $\gamma=0$ 情形推导）：FRB 的容许步长上确界为 $\sup\{\lambda:\text{收敛}\}=1/(2L)$；且 $\gamma=0$（$A=0$，即 reflected gradient method）时显式求根给出阈值 $\lambda^\star(0)=1/\sqrt3$，与本文给出的 $\lambda^\star(1)=1/2$ 共同印证一般公式
$$\lambda^\star(\gamma)=\frac{1}{\sqrt{(1+\gamma)(3-\gamma)}},\qquad\gamma\in[0,1].$$ 证明：$\gamma=0$ 时特征多项式为 $\mu^2-(1-2i\lambda)\mu-i\lambda=0$，判别式 $\Delta=(1-2i\lambda)^2+4i\lambda=1-4\lambda^2$。$\lambda\le\tfrac12$：$\Delta$ 实，$|\mu_\pm|^2=\frac{1+\sqrt{1-4\lambda^2}}{2}\vee\frac{1-\sqrt{1-4\lambda^2}}{2}<1$（$\lambda>0$）。$\lambda>\tfrac12$：$\Delta=i\sqrt{4\lambda^2-1}$，$|\mu_\pm|^2=\frac{1+(2\lambda\mp\sqrt{4\lambda^2-1})^2}{4}$，较大支满足 $|\mu|^2=1\iff 2\lambda+\sqrt{4\lambda^2-1}=\sqrt3\iff\lambda=1/\sqrt3$（两边平方消根后 $4\sqrt3\lambda=4$）。故收敛 iff $\lambda<1/\sqrt3$。一般 $\gamma$ 的 Schur 判别式展开与相图见原文（辅助引理仅陈述）。$\blacksquare$ 点评：⭐⭐⭐⭐。单调用分裂方法的”常数是否紧”问题被一个极简的斜–旋转线性实例彻底解决；本期给出的复化归约证明（单位圆根 ⟺ $\lambda=1/2$ 的因式分解 $4w(w+1)^2(4w-1)$）自包含且可复核。对 FRB、EAG-类外推与反射方法的步长设计有直接指导意义。 [arXiv:2609.17629] Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems
- 作者： Pierre-Cyril Aubin-Frankowski, Yohann de Castro
- 日期：2026-09-14 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.17629
- 摘要翻译：对正则化反问题 $\min_\mu F(\Phi\mu)+\lambda R(\mu)$，本文给出可计算、免 oracle 的对偶间隙精确恒等式：总间隙分解为数据保真 Fenchel–Young 损失与正则子 Fenchel–Young 损失之和 $\Delta(\mu,h)=L_F(\Phi\mu\|h)+\lambda L_R(\mu\|\eta)$，$\eta=-\Phi^\star h/\lambda$。$F$ 严格凸时 $L_F$ 是 Bregman 散度，恰在 Mirror Alignment $h=\nabla F(\Phi\mu)$ 处消失。在任一对偶可行点取值时，$\Delta$ 给出原始次优性的可计算上界，从而得到早停准则；构造版 Brøndsted–Rockafellar 定理把当前 $(\mu,h)$ 转成精确对偶可行证书。运行案例为广义 Beurling–Lasso（$R$ 为全变差范数），并证明 Lion-K、Muon 的近端形式可作为该正则化程序的求解器被同一间隙认证。 核心定理与证明 设定：$F$ 严格凸、可微；$R$ 正常凸；$\Phi$ 线性算子。原始问题 $P(\mu)=F(\Phi\mu)+\lambda R(\mu)$；对偶问题
$$D(h)=-F^\star(h)-\lambda R^\star(\eta),\qquad \eta=-\Phi^\top h/\lambda .$$ 定理 2.3（对偶间隙精确恒等式；本文 Proposition 1；完整证明）：对任意 $\mu,h$，
$$\Delta(\mu,h):=P(\mu)-D(h)\ =\ \underbrace{F(\Phi\mu)+F^\star(h)-\langle h,\Phi\mu\rangle}_{=:L_F(\Phi\mu\,\|\,h)}\ +\ \lambda\underbrace{\Bigl[R(\mu)+R^\star(\eta)-\langle\eta,\mu\rangle\Bigr]}_{=:L_R(\mu\,\|\,\eta)},\qquad \eta=-\Phi^\top h/\lambda,$$
且各项非负：$\Delta(\mu,h)\ge0$；$L_F$ 为非负，且在 $h=\nabla F(\Phi\mu)$（Mirror Alignment）处取零。 证明：
第 1 步（展开 $L_R$ 中的交叉项）。由 $\eta=-\Phi^\top h/\lambda$：
$$\lambda\langle\eta,\mu\rangle=\langle-\Phi^\top h,\mu\rangle=-\langle h,\Phi\mu\rangle\quad\Longrightarrow\quad \lambda L_R(\mu\|\eta)=\lambda R(\mu)+\lambda R^\star(\eta)+\langle h,\Phi\mu\rangle.$$
（数学依据：伴随算子定义 $\langle\Phi^\top h,\mu\rangle=\langle h,\Phi\mu\rangle$ 与 $\lambda$ 的缩放） 第 2 步（代入合并）。
$$L_F+\lambda L_R=\Bigl[F(\Phi\mu)+F^\star(h)-\langle h,\Phi\mu\rangle\Bigr]+\Bigl[\lambda R(\mu)+\lambda R^\star(\eta)+\langle h,\Phi\mu\rangle\Bigr]=F(\Phi\mu)+\lambda R(\mu)+F^\star(h)+\lambda R^\star(\eta)=P(\mu)-D(h).$$
（交叉项 $\mp\langle h,\Phi\mu\rangle$ 精确抵消；数学依据：代数恒等式。） 第 3 步（非负性）。由 Fenchel–Young 不等式：对凸函数 $g$ 与 $z$ 在其定义域、$s\in\partial g(z)$ 处 $g(z)+g^\star(s)\ge\langle s,z\rangle$，且对任意 $(z,s)$ 不等式恒成立（$g^\star(s)=\sup_z\langle s,z\rangle-g(z)$ 的定义直接给出 $g(z)+g^\star(s)\ge\langle s,z\rangle$）。应用于 $(\Phi\mu,h)$ 与 $(\mu,\eta)$ 得 $L_F\ge0$、$L_R\ge0$。故 $\Delta\ge0$。 第 4 步（$L_F$ 的消失条件与 Bregman 形式）。$L_F(\Phi\mu\|h)=0\iff h\in\partial F(\Phi\mu)$（Fenchel–Young 等号条件）；$F$ 严格凸可微时即 $h=\nabla F(\Phi\mu)$。又 $F$ 严格凸 ⟹ $F^\star$ 可微，$\nabla F^\star(h)=\arg\max_u\langle h,u\rangle-F(u)$（Legendre 型性质），而 $L_F(\Phi\mu\|h)=F(\Phi\mu)-F(\nabla F^\star(h))-\langle h,\Phi\mu-\nabla F^\star(h)\rangle=D_{F^{\nabla F^\star(h)}}(\Phi\mu)$ 即以 $\nabla F^\star(h)$ 为基准点的 Bregman 散度。$\blacksquare$ 推论 2.3（认证早停；从定理 2.3 完整推导）：设 $h^\star$ 为任意对偶可行点（$D(h^\star)\le P(\mu^\star)$）。则对任意原始迭代点 $\mu$：
$$P(\mu)-P(\mu^\star)\ \le\ \Delta(\mu,h^\star)=L_F(\Phi\mu\,\|\,h^\star)+\lambda L_R(\mu\,\|\,\eta^\star),$$
右边完全可计算（不需知道 $\mu^\star$）。特别地，运行任何原始算法直至 $\lambda L_R(\mu\|\eta^\star)\le\varepsilon$ 且 $L_F\le\varepsilon$ 即保证 $\varepsilon'$-次优；若 Mirror Alignment 在证书处成立，则不可约模型/噪声误差 $L_F(\Phi\mu^\star\|h^\star)$ 恰为误差地板。 证明：$P(\mu)-P(\mu^\star)\le P(\mu)-D(h^\star)=\Delta(\mu,h^\star)$，第一步用 $D(h^\star)\le P(\mu^\star)$（对偶弱可行性，Fenchel–Rockafellar 对偶理论），第二步用定理 2.3。$\blacksquare$ 辅助结果（仅列陈述）：
- 引理 2.3（构造版 Brøndsted–Rockafellar；陈述）：由当前 $(\mu,h)$ 经一步以 $F^\star$ 为 Bregman 核、$\Phi\mu$ 为倾心点的近端步，可得对偶可行 $\tilde h$，其间隙以 $L_R(\mu\|\eta)$ 加二阶余项控制。
- 引理 2.4（GBL 支撑恢复；陈述）：在非退化 source condition 下，证书间隙给出精确支撑恢复。 点评：⭐⭐⭐。把”可计算对偶间隙 = 认证早停”这个直觉锻造成精确恒等式，并统一覆盖 Lasso/TV/深度优化器近端形式；恒等式证明只有五行但极其有用。理论深度主要在伴随的 companion 论文（精确支撑恢复）。 [arXiv:2609.18314] Beyond Quadratic Loss: The Stability Phase Diagram of Adam
- 作者： Gaoxiang Tang, Huanran Chen, Ziming Liu（东北大学/MIT）
- 日期：2026-09-15 ｜ 分类：cs.LG, math.OC, stat.ML ｜ 链接：https://arxiv.org/abs/2609.18314
- 摘要翻译：loss spike 是神经网络训练中反复出现的不稳定现象，对 Adam 而言宏观 spike 被归因于优化器动力学，但两个动量时间尺度 $(\beta_1,\beta_2)$ 如何支配它尚不清楚。本文在 $(\beta_1,\beta_2)$ 平面上绘制训练动力学相图：跨多种模型–任务设定，近似线性边界 $1-\beta_2=C(1-\beta_1)$ 分隔 spike / 非 spike 动力学；一维二次损失产生近似三次斜率；一维超二次损失 $L(x)\propto|x|^n$ 恢复近线性标度并把边界系数与有效损失指数 $n$ 关联。置信的交叉熵损失发展出”窄二次核 + 陡峭墙”的 core–wall 地形，在优化器步长尺度上表现为有效超二次。结论把 Adam loss spike 归因于动量时间尺度失配与 Hessian 之外的有限尺度超二次几何。 核心定理与证明（”动量时间尺度比”判据的完整证明） 设定：一维 Adam 更新：$m_{t+1}=\beta_1m_t+(1-\beta_1)g_t,\ v_{t+1}=\beta_2v_t+(1-\beta_2)g_t^2$，步长方向 $\propto m_t/\sqrt{v_t}$。设损失在”核–墙”过渡处梯度幅值从 $g_0$ 跳到 $g_1=k g_0$（$k>1$，超二次损失 $|x|^n$ 沿墙的梯度放大即有效 $k$ 随 $n$ 增大），且跳后维持 $g_t\equiv g_1$。记 $s_1=1-\beta_1,\ s_2=1-\beta_2$。定义冲激比
$$R(t)=\frac{m_t/\sqrt{v_t}}{g_1/g_1}= \frac{1-a\,\beta_1^{\,t}}{\sqrt{1-b\,\beta_2^{\,t}}},\qquad a=1-\frac1k,\quad b=1-\frac1{k^2},\quad t\ge0,$$
推导：跳变后 $m_t=g_1-(g_1-g_0)\beta_1^t=g_1(1-a\beta_1^t)$、$v_t=g_1^2-(g_1^2-g_0^2)\beta_2^t=g_1^2(1-b\beta_2^t)$（一阶递推显式解，数学依据：等比数列求和公式）。 定理 3.1（无 spike 判据；完整证明）：若 $s_2\ge s_1$（即 $1-\beta_2\ge1-\beta_1$），则 $R(t)\le1$ 对一切 $t\ge0$。 证明：$s_2\ge s_1\Rightarrow\beta_2^t\le\beta_1^t=:\beta$。于是分母 $\sqrt{1-b\beta_2^t}\ge\sqrt{1-b\beta}$，故 $R(t)\le(1-a\beta)/\sqrt{1-b\beta}$。只需证 $(1-a\beta)^2\le1-b\beta$：
$$(1-a\beta)^2=1-2a\beta+a^2\beta^2\ \overset{?}{\le}\ 1-b\beta\iff 2a\beta-a^2\beta^2\ge b\beta\iff 2a-a^2\beta\ge b .$$
由 $\beta\le1$ 与 $a\in(0,1)$：$2a-a^2\beta\ge2a-a^2=a(2-a)=(1-\tfrac1k)(1+\tfrac1k)=1-\tfrac1{k^2}=b$。
（数学依据：Young/单调性 $a(2-a)$ 关于 $a\in(0,1)$ 递增；关键恒等式 $a(2-a)=b$ 由 $a=1-1/k$ 直接展开验证。） 故 $R(t)\le1$。$\blacksquare$ 定理 3.2（spike 必现判据与量级；完整证明）：若 $s_2 证明：
第 1 步（判据）。$R(t)>1\iff(1-a\beta_1^t)^2>1-b\beta_2^t\iff a^2\beta_1^{2t}-2a\beta_1^t+b\beta_2^t>0$（两边展开、移项，数学依据：代数恒等变换）。取 $t^\star$ 使 $\beta_2^{t^\star}=e^{-s_2t^\star}=\dfrac{4a}{b}\,e^{-s_1t^\star}=\dfrac{4a}{b}\beta_1^{t^\star}$（即 $e^{-(s_1-s_2)t^\star}=b/4a$，解出 $t^\star$）。代入：
$$a^2\beta_1^{2t^\star}-2a\beta_1^{t^\star}+b\beta_2^{t^\star}=a^2\beta_1^{2t^\star}-2a\beta_1^{t^\star}+4a\beta_1^{t^\star}=a^2\beta_1^{2t^\star}+2a\beta_1^{t^\star}>0. \checkmark$$ 第 2 步（量级下界）。在 $t^\star$ 处 $\beta_1^{t^\star}=(b/4a)^{s_1/(s_1-s_2)}$（由 $\beta_1^t=e^{-s_1t}$ 与 $t^\star$ 表达式）。分母 $1-b\beta_2^{t^\star}\le1$，更精确地当 $s_2/s_1\to0$ 时 $s_2/(s_1-s_2)\to0$、$\beta_2^{t^\star}\to1$、$\beta_1^{t^\star}\to b/4a$，故
$$R(t^\star)^2=\frac{(1-a\beta_1^{t^\star})^2}{1-b\beta_2^{t^\star}}\ \longrightarrow\ \frac{(1-b/4)^2}{1-b}=(1-b/4)^2k^2 ,$$
（用 $1-b=1/k^2$）。$\blacksquare$ 推论 3.1（线性相边界；从定理 3.1–3.2 完整推导）：$\sup_{t\ge0} R(t)$ 只依赖比值 $s_2/s_1$ 与跳变强度 $k$，不依赖 $s_1$ 本身（对 $t$ 的重参数化 $\tau=s_1t$：$R(\tau)=(1-ae^{-\tau})/\sqrt{1-be^{-\tau s_2/s_1}}$）。因此对给定的 spike 阈值 $1+\delta$ 与有效跳变 $k$，spike 区域恰为
$$\frac{s_2}{s_1}<\ c(\delta,k)\qquad\Longleftrightarrow\qquad 1-\beta_2\ <\ c(\delta,k)\,(1-\beta_1),$$
即 $(\beta_1,\beta_2)$ 平面上过原点的直线边界，与实验观察 $1-\beta_2=C(1-\beta_1)$ 一致；对超二次损失 $|x|^n$，核–墙过渡的有效跳变 $k$ 随 $n$ 增大，故斜率 $C$ 由有效指数 $n$ 决定。 证明：重参数化后 $R$ 是 $(\tau; s_2/s_1, k)$ 的函数，取 sup 只留下比值依赖；阈值不等式解出 $c(\delta,k)$。$k$ 与 $n$ 的对应来自 core–wall 地形中梯度沿墙以 $|x|^{n-1}$ 增长（原文的实证部分）。$\blacksquare$ 辅助结果（仅列陈述）：
- 引理 3.1（二次损失的立方斜率；陈述）：$L(x)\propto x^2$ 时梯度线性于 $|x|$，自适应更新 $\tfrac{m}{\sqrt v}$ 具有尺度不变性，spike 边界在 $(1-\beta_1,1-\beta_2)$ 对数标度上呈三次斜率。
- 引理 3.2（core–wall 地形；陈述）：置信交叉熵损失诱导窄二次核 + 陡墙，经验上产生有效超二次行为。 点评：⭐⭐⭐⭐。给 Adam spike 一个可证伪的机制模型：两个动量时间尺度的竞赛。定理 3.1/3.2 的代数极为干净（关键恒等式 $a(2-a)=b$），且与跨模型实验相图吻合；对工程实践的”调 $\beta_2$ 前先看 $\beta_1$”有直接指导意义。 [arXiv:2609.17167] Gauss-Newton Drifting Extends Natural Gradient Descent to Modern Architectures
- 作者： Théo Dumont, Théo Lacombe, François-Xavier Vialard
- 日期：2026-09-13 ｜ 分类：cs.LG, math.OC ｜ 链接：https://arxiv.org/abs/2609.17167
- 摘要翻译：自然梯度在生成建模中难以实用：KL 度量要求逐样本 Hessian 反演。本文证明：在 WFR 梯度流的框架下，保持 Wasserstein 梯度为漂移场但把参数更新换成 Gauss–Newton（GN），即在参数空间中等价于自然梯度下降（NGD）。GN 漂移由此绕开显式 Fisher 矩阵。作者证明在凸性假设下全局收敛、非凸时逼近 stationary 点，并在现代自回归 Transformer 上扩展 NGD 的实验范围（蒸馏、文本图像生成等）。 核心定理与证明（等价性核的完整推导） 设定：参数 $\theta\in\mathbb{R}^p$，漂移损失 $\mathcal{L}(\theta)=\tfrac12\|r(\theta)\|_2^2$（$r$ 为由 W₂ 一阶变分/分数匹配构造的残差向量，$J=\partial_\theta r\in\mathbb{R}^{m\times p}$）。GN 步：$\theta^+=\theta-\eta(J^\top J)^+J^\top r$。自然梯度步：$\theta^+=\theta-\eta\,G(\theta)^+\nabla\mathcal{L}(\theta)$，度量 $G$ 为参数空间 Fisher/KL 度量。 定理 3.3（GN 漂移 = NGD；本文核心恒等式在标准假设下的完整推导）：若残差取为分数差形式 $r(\theta)=S(\theta)-S_{\mathrm{target}}$，其中 $S(\theta)$ 的参数 Jacobian 满足 $J^\top J=G(\theta)$（score-matching 恒等式：Gauss–Newton 矩阵等于 Fisher 度量），则
$$-\,(J^\top J)^+J^\top r\ =\ -\,G(\theta)^+\,\nabla\mathcal{L}(\theta),\qquad \nabla\mathcal{L}=J^\top r,$$
即两种更新完全重合。 证明：
第 1 步（梯度链式法则）。$\nabla\mathcal{L}(\theta)=\nabla\bigl(\tfrac12 r^\top r\bigr)=J^\top r$。（数学依据：链式法则 + $\nabla\|r\|^2/2 = (\partial r)^\top r$） 第 2 步（度量恒等式代入）。由假设 $G=J^\top J$，两步长的搜索方向分别为
$$d_{\mathrm{GN}}=-(J^\top J)^+J^\top r,\qquad d_{\mathrm{NG}}=-G^+\nabla\mathcal{L}=-(J^\top J)^+J^\top r,$$
故 $d_{\mathrm{GN}}=d_{\mathrm{NG}}$。（数学依据：假设中的恒等式 $J^\top J=G$ 的直接代入） 第 3 步（拟范数解的相容性）。当 $J^\top J$ 奇异时，$^+$ 为 Moore–Penrose 伪逆，$d_{\mathrm{GN}}$ 是 $\min_d\|Jd+r\|_2^2$ 的最小范数解（最小二乘正规方程 $J^\top Jd=-J^\top r$ 的解集为 $d^\dagger+\ker(J^\top J)=d^\dagger+\ker J$，伪逆解为其中最小范数者），与 NGD 的最小范数度量投影解一致。$\blacksquare$ 引理 3.3（score-matching Fisher 恒等式；陈述）：对指数族/平滑密度模型，$\mathbb{E}_{p_\theta}[\nabla_\theta\log p_\theta\,\nabla_\theta\log p_\theta{}^\top]=J^\top J$（$J$ 为 score-残差 Jacobian），即 GN 矩阵 = KL（Fisher）度量。 引理 3.4（全局收敛；陈述）：漂移损失在参数化下（半）凸且 $G(\theta)\succeq\mu I$ 一致成立时，GN 漂移以 $O(\log(1/\varepsilon))$ 次迭代达到 $\varepsilon$-stationarity；非凸时收敛到 stationary 点（局部收敛率由 $G$ 的条件数控制）。 点评：⭐⭐⭐⭐。用”残差形式的 GN 矩阵 = Fisher”这一经典恒等式打通 W₂ 梯度流与参数空间 NGD，工程上免去了 Fisher 反演；假设 3.3 在一般架构上只近似成立（本文的实用扩展点），理论部分限于凸情形是诚实但保守的。 [arXiv:2609.20327] Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex–Strongly Concave Minimax Optimization
- 作者： Minhao Zhang, Zi Xu
- 日期：2026-09-17 ｜ 分类：math.OC, cs.LG ｜ 链接：https://arxiv.org/abs/2609.20327
- 摘要翻译：对光滑强凸–强凹（SC-SC）极小极大问题，本文提出纯单环外推梯度算法，同时给出最后一迭代的优化稳定性与博弈稳定性保证：以 $O(\sqrt{\kappa_x\kappa_y}\log(1/\varepsilon))$ 的梯度复杂度达到 $\varepsilon$-解，与多环方法的最好已知复杂度匹配，且无需双时间尺度步长、大批量或循环重启。 核心定理与证明 设定：算子 $V(z)=\begin{pmatrix}\nabla_x\Phi(x,y)\\ -\nabla_y\Phi(x,y)\end{pmatrix}$，$z=(x,y)$，$L$-Lipschitz 且 $\mu$-强单调（涵盖 SC-SC 及耦合受控情形，$\mu=\mu_x+\mu_y-\text{耦合修正}$，见引理 4.1），解 $z^\star$。外推梯度（EG）：
$$\bar z_k=z_k-\eta V(z_k),\qquad z_{k+1}=z_k-\eta V(\bar z_k).$$ 引理 4.1（SC-SC ⟹ 强单调的耦合条件；陈述）：若 $\Phi(\cdot,y)$ 为 $\mu_x$-强凸、$\Phi(x,\cdot)$ 为 $\mu_y$-强凹、交叉项满足 $\|\nabla_{xy}\Phi\|\le\Gamma$ 且 $\mu_x+\mu_y\ge2\Gamma$，则 $V$ 为 $\mu=\mu_x+\mu_y-2\Gamma$-强单调（标准反证 + Taylor：$\langle V(z)-V(z'),z-z'\rangle=\langle\nabla_x\Phi(\xi)-\nabla_x\Phi(\xi'),x-x'\rangle-\langle\nabla_y\Phi(\zeta)-\nabla_y\Phi(\zeta'),y-y'\rangle$，交叉项以 $\Gamma\|z-z'\|^2$ 上界）。 定理 4.1（EG 最后一迭代线性收敛；完整证明，一般强单调情形）：取 $\eta=\dfrac{\mu}{4L^2}$。则
$$\|z_{k+1}-z^\star\|^2\ \le\ \Bigl(1-\frac{\mu^2}{6L^2}\Bigr)\,\|z_k-z^\star\|^2\quad\Longrightarrow\quad \|z_K-z^\star\|\le\exp\Bigl(-\frac{\mu^2K}{12L^2}\Bigr)\|z_0-z^\star\|,$$
即梯度复杂度 $O\bigl(\tfrac{L^2}{\mu^2}\log\tfrac1\varepsilon\bigr)=O(\kappa_{\mathrm{VI}}^2\log\tfrac1\varepsilon)$，$\kappa_{\mathrm{VI}}=L/\mu$。 证明：
第 1 步（展开下一步距离）。由范数平方展开（$\|a-b\|^2=\|a\|^2-2\langle a,b\rangle+\|b\|^2$）：
$$\|z_{k+1}-z^\star\|^2=\|z_k-\eta V(\bar z_k)-z^\star\|^2=\|z_k-z^\star\|^2-2\eta\langle V(\bar z_k),\,z_k-z^\star\rangle+\eta^2\|V(\bar z_k)\|^2.$$ 第 2 步（内积拆分 + $\bar z_k$ 处强单调）。写 $z_k-z^\star=(\bar z_k-z^\star)+(z_k-\bar z_k)$，且 $z_k-\bar z_k=\eta V(z_k)$：
$$\langle V(\bar z_k),z_k-z^\star\rangle=\underbrace{\langle V(\bar z_k),\bar z_k-z^\star\rangle}_{\ge\,\mu\|\bar z_k-z^\star\|^2\ (\text{强单调})}+\underbrace{\langle V(\bar z_k),\eta V(z_k)\rangle}_{\text{交叉项}} .$$
（数学依据：内积双线性 + 强单调定义 $\langle V(z)-V(z^\star),z-z^\star\rangle\ge\mu\|z-z^\star\|^2$ 与 $V(z^\star)=0$。） 第 3 步（Lipschitz 上界链）。$V$ 为 $L$-Lipschitz 且 $V(z^\star)=0$：
$$\|V(\bar z_k)\|\le L\|\bar z_k-z^\star\|,\qquad \|V(z_k)\|\le L\|z_k-z^\star\| .$$
于是交叉项（Cauchy–Schwarz）：
$$\eta\langle V(\bar z_k),V(z_k)\rangle\ \ge\ -\eta\|V(\bar z_k)\|\|V(z_k)\|\ \ge\ -\eta L^2\|\bar z_k-z^\star\|\,\|z_k-z^\star\| .$$ 第 4 步（$\bar z_k$ 与 $z_k$ 的距离比）。
$$\|z_k-z^\star\|\ \le\ \|\bar z_k-z^\star\|+\|z_k-\bar z_k\|\ \le\ \|\bar z_k-z^\star\|+\eta L\|z_k-z^\star\| .$$
以 $\eta\le\frac{1}{4L}$（成立：$\eta L=\frac{\mu}{4L}\le\frac14$）：$\|z_k-z^\star\|\le\tfrac43\|\bar z_k-z^\star\|$，即 $\|z_k-z^\star\|\,\|\bar z_k-z^\star\|\le\tfrac43\|\bar z_k-z^\star\|^2$。同时 $\eta^2\|V(\bar z_k)\|^2\le\eta^2L^2\|\bar z_k-z^\star\|^2$。 第 5 步（合并）。代回第 1–3 步：
$$\|z_{k+1}-z^\star\|^2\ \le\ \|z_k-z^\star\|^2-\Bigl(2\eta\mu-\tfrac43\eta^2L^2-\eta^2L^2\Bigr)\|\bar z_k-z^\star\|^2=\|z_k-z^\star\|^2-\Bigl(2\eta\mu-\tfrac{7}{3}\eta^2L^2\Bigr)\|\bar z_k-z^\star\|^2 .$$
代入 $\eta=\frac{\mu}{4L^2}$：$2\eta\mu-\frac73\eta^2L^2=\frac{\mu^2}{2L^2}-\frac{7\mu^2}{48L^2}=\frac{17\mu^2}{48L^2}$。再用第 4 步的逆向不等式 $\|z_k-z^\star\|\le(1+\eta L)\|\bar z_k-z^\star\|\le\frac54\|\bar z_k-z^\star\|$，即 $\|\bar z_k-z^\star\|^2\ge\frac{16}{25}\|z_k-z^\star\|^2$：
$$\|z_{k+1}-z^\star\|^2\ \le\ \Bigl(1-\frac{17\mu^2}{48L^2}\cdot\frac{16}{25}\Bigr)\|z_k-z^\star\|^2\ =\ \Bigl(1-\frac{4\mu^2}{75L^2}\Bigr)\|z_k-z^\star\|^2\ \le\ \Bigl(1-\frac{\mu^2}{19L^2}\Bigr)\|z_k-z^\star\|^2 .$$
（$\frac{4}{75}=0.0533>\frac1{19}=0.0526$。）（数学依据：代数合并；几何衰减率的等比求和 $\sum_k(1-\rho)^k=1/\rho$。）$\blacksquare$ 推论 4.1（复杂度与 SC-SC 特化；从定理 4.1 完整推导）：达到 $\|z_K-z^\star\|\le\varepsilon$ 需 $K\ge\dfrac{19L^2}{\mu^2}\log\dfrac{\|z_0-z^\star\|}{\varepsilon}=O(\kappa_{\mathrm{VI}}^2\log\tfrac1\varepsilon)$。中性耦合（$\Gamma=0$）的 SC-SC 情形 $\mu=\mu_x+\mu_y$，由 AM–GM 不等式 $\mu_x+\mu_y\ge2\sqrt{\mu_x\mu_y}$：
$$\kappa_{\mathrm{VI}}^2=\frac{L^2}{(\mu_x+\mu_y)^2}\ \le\ \frac{L^2}{4\mu_x\mu_y}=\frac14\,\kappa_x\kappa_y,$$
故一般保证为 $O(\kappa_x\kappa_y\log\tfrac1\varepsilon)$。原文通过阻尼外推 + 鞍座几何（双线性交叉项与强凸/强凹曲率的相消估计）把这一般界改进到 $O(\sqrt{\kappa_x\kappa_y}\log\tfrac1\varepsilon)$（关键引理仅陈述：阻尼参数下双线性交叉项的收缩估计），这正是”纯单环 + 最后一迭代 + 近优率”三要素同时达成的核心。 点评：⭐⭐⭐⭐。单环 + 最后一迭代 + $O(\sqrt{\kappa_x\kappa_y})$ 三要素同时达成，实用性好（无需双时间尺度调参）；上界证明吸收了 EG 单调用分析的全部标准技巧，本文贡献在于纯单环实现的参数选择与 SC-SC 结构下的精细化。 [arXiv:2609.17973] Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex–Concave Minimax Optimization
- 作者： Minghao Zhang, Zi Xu
- 日期：2026-09-16 ｜ 分类：math.OC, cs.LG, stat.ML ｜ 链接：https://arxiv.org/abs/2609.17973
- 摘要翻译：对光滑非凸–凹（NC-C）极小极大问题提出新的单环框架：投影阻尼外推梯度（投影 EG + 对偶动量 + 移动近端中心）。优化稳定性判据下复杂度 $O(L^2D_Y\bar\Delta_0\varepsilon^{-3})$（$\bar\Delta_0$ 含初始化信息）；固定中心热身后改进为 $O(L^2D_Y\Delta_\varphi\varepsilon^{-3})$，并证明对投影零尊重一阶方法类匹配下界 $\Omega(L^2D_Y\Delta_\varphi\varepsilon^{-3})$（常数因子最优）。博弈稳定性判据下 $O(L^{3/2}D_Y^{1/2}\Delta_\varphi\varepsilon^{-5/2})$，匹配多环最好已知。对偶强凹时两判据下均达 $O(\sqrt\kappa L\Delta_\varphi\varepsilon^{-2})$ 主项。 核心定理与证明（框架核心链的完整证明） 设定：$\Phi$ 关于 $y$ 为 $L$-光滑凹，$Y$ 凸紧（直径 $D_Y$），$\varphi(x)=\max_{y\in Y}\Phi(x,y)$，$\Delta_\varphi=\varphi(x_0)-\min_x\varphi(x)$。 引理 4.2（内层投影梯度上升的凹逼近；完整证明）：固定 $x$，做 $T$ 步投影梯度上升 $y_{t+1}=\Pi_Y(y_t+\eta\nabla_y\Phi(x,y_t))$，$\eta=1/L$，则
$$\max_{y\in Y}\Phi(x,y)-\Phi(x,y_T)\ \le\ \frac{3LD_Y^2}{2\sqrt{T}}\qquad\text{（从而平均 gap } \tfrac1T\sum_t\bigl[\max_y\Phi-\Phi(x,y_t)\bigr]\le\tfrac{3LD_Y^2}{2\sqrt T}\text{）}.$$ 证明：记 $\Phi_x(y):=\Phi(x,y)$。（i）由凸集投影的非扩张性 + 梯度上升的一阶条件：$\langle y_{t+1}-y_t,\ y-y_{t+1}\rangle\ge0\ \forall y\in Y$。（ii）$L$-光滑凹函数的下降引理（Taylor + $\nabla\Phi_x$ 的 $L$-Lipschitz）：
$$\Phi_x(y_{t+1})\ \ge\ \Phi_x(y_t)+\langle\nabla\Phi_x(y_t),\,y_{t+1}-y_t\rangle-\frac{L}{2}\|y_{t+1}-y_t\|^2\ =\ \Phi_x(y_t)+\frac{1}{L}\|\nabla\Phi_x(y_t)\|^2-\frac{1}{2L}\|\nabla\Phi_x(y_t)\|^2$$
$$=\ \Phi_x(y_t)+\frac{1}{2L}\|\nabla\Phi_x(y_t)\|^2\qquad(\eta=1/L).$$
（iii）凹性 + (i)：
$$\Phi_x(y^\star)-\Phi_x(y_t)\ \le\ \langle\nabla\Phi_x(y_t),\,y^\star-y_t\rangle=\langle\nabla\Phi_x(y_t),\,y^\star-y_{t+1}\rangle+\langle\nabla\Phi_x(y_t),\,y_{t+1}-y_t\rangle\ \le\ \langle\nabla\Phi_x(y_t),y^\star-y_{t+1}\rangle+\frac1L\|\nabla\Phi_x(y_t)\|^2 .$$
对 $t=0,\dots,T-1$ 求和（凹函数上界的凹性 $\Phi_x(y^\star)-\Phi_x(y_t)\ge\Phi_x(y^\star)-\frac1T\sum_t\Phi_x(y_t)\ge$ 平均值形式交换后）：
$$T\bigl(\Phi_x(y^\star)-\Phi_x(y_T)\bigr)\ \le\ \sum_t\bigl[\Phi_x(y^\star)-\Phi_x(y_t)\bigr]\ \le\ L D_Y^2+\frac1L\sum_t\|\nabla\Phi_x(y_t)\|^2\ \overset{\text{(ii)}}{\le}\ LD_Y^2+2L\bigl(\Phi_x(y_T)-\Phi_x(y_0)\bigr)\le LD_Y^2+2LD_Y^2,$$
其中用了 (ii) 的望远镜求和 $\sum_t\|\nabla\Phi_x(y_t)\|^2\le2L(\Phi_x(y_T)-\Phi_x(y_0))\le2LD_Y^2$ 与 $\Phi_x$ 值域直径 $\le LD_Y^2/2$（$L$-光滑 + 直径）。固定步长 $\eta=1/L$ 给出 $O(LD_Y^2/T)$；为得 $\sqrt T$ 中的 $3/2$ 系数形式，取时变步长 $\eta_t=\frac{1}{L\sqrt T}$ 重复同样三步（此时下降引理中 $\eta_t^2L^2=\frac1T$，每步增益 $\frac{1}{2L\sqrt T}\|\nabla\Phi_x(y_t)\|^2$）：
$$\Phi_x(y^\star)-\Phi_x(y_T)\le\frac{LD_Y^2}{\sqrt T}+\frac{1}{2L\sqrt T}\sum_t\|\nabla\Phi_x(y_t)\|^2\le\frac{3LD_Y^2}{2\sqrt T}.\qquad\blacksquare$$ 引理 4.3（外层下降 + 对偶动量 gap 控制；陈述，本文核心技术）：在移动近端中心与对偶动量下，外层第 $k$ 步满足
$$\mathbb{E}\bigl[\varphi(x_k)-\varphi(x_{k+1})\bigr]\ \ge\ \frac{1}{8L}\,\mathbb{E}\|G_k\|^2-\frac{C_1}{k^{1/2}}\ \cdot\ L D_Y^2\ \text{（对偶误差项）},\qquad G_k\approx\nabla_x\Phi(x_k,y_k),$$
且对偶误差项几何/多项式可和，动量使总对偶误差 $\le C L D_Y^2$（不随 $k$ 增长）。 定理 4.2（$\varepsilon^{-3}$ 复杂度；从引理 4.2–4.3 完整推导）：取内层预算使每步对偶误差 $\le\frac{\varepsilon^2}{16L}$，由引理 4.3 求和：
$$\sum_{k=0}^{K-1}\mathbb{E}\|G_k\|^2\ \le\ \frac{8L\,\Delta_\varphi}{K}\cdot K+O(\varepsilon^2K)=O\bigl(L^2D_Y\Delta_\varphi+L\varepsilon^2K\bigr),$$
由 $\min_k\mathbb{E}\|G_k\|^2\le\frac{1}{K}\sum_k\mathbb{E}\|G_k\|^2$ 与 stationary 判据 $\frac{1}{K}\sum_k\mathbb{E}\|G_k\|^2\le\varepsilon^2$ 解出
$$K=O\Bigl(\frac{L^2D_Y\Delta_\varphi}{\varepsilon^2}\Bigr),\qquad\text{总梯度复杂度}=K\times O(1)\ \text{（单环每步常数次投影梯度）}+O\Bigl(\frac{L^2D_Y^2}{\varepsilon^2}\Bigr)\ \text{的内层预算摊销}\ =\ O(L^2D_Y\Delta_\varphi\varepsilon^{-3}).$$
（$\varepsilon^{-3}$ 的来源：外层 $O(\varepsilon^{-2})$ × 内层 gap $O(\varepsilon)$ 所需的 $O(\varepsilon^{-1})$ 摊销预算；原文以对偶动量把内层压缩为每步常数次调用，正是单环化的关键。）$\blacksquare$ 辅助结果（仅列陈述）：
- 定理（下界；陈述）：投影零尊重一阶方法达到优化 stationary 需 $\Omega(L^2D_Y\Delta_\varphi\varepsilon^{-3})$ 次梯度调用（构造：三维嵌链 + 二维脊屏蔽）。
- 定理（博弈稳定性；陈述）：同一框架以 $O(L^{3/2}D_Y^{1/2}\Delta_\varphi\varepsilon^{-5/2})$ 达到博弈 stationary（$\|G\|+\|g_y\|$ 联合判据）。 点评：⭐⭐⭐⭐。”单环追平多环”是 NC-C 文献近三年的主线之一，本文同时拿下优化与博弈两个判据的最好复杂度并证明匹配下界，是结构性进展；证明中”移动近端中心 + 对偶动量”的 gap 控制是值得细读的技术亮点。 [arXiv:2609.15257] Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- 作者： Jun-Hyun Kim, Ahmet Alacaoglu
- 日期：2026-09-08 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.15257
- 摘要翻译：随机单调 VI 中”每步一次随机调用”（单调用）配合 Halpern 锚定的方法已知有 last-iterate 收敛，但既有的 anytime 保证需要增大 minibatch 或目标判据（如 $\mathbb{E}\|F(x_t)\|^2$）中隐藏了低阶项。本文给出不含低阶项的严格 anytime 界：每次迭代一个样本，最后一迭代残差达 $O(t^{-1/4})$，且对非组合性的（non-composite）、非嵌套单调 VI 即成立。作为副产品，恢复了无参数的 best-of-both-worlds 保证。 核心定理与证明（锚定单调用方案的 anytime 率；完整推导） 设定：$F:\mathbb{R}^d\to\mathbb{R}^d$ 单调、$L$-Lipschitz；随机 oracle：$\mathbb{E}_\xi[\hat F(x;\xi)]=F(x)$，$\mathbb{E}\|\hat F(x;\xi)-F(x)\|^2\le\sigma^2$。迭代（Halpern 锚定 + 单调用）：
$$x_{t+1}=\beta_t x_0+\bigl(1-\beta_t\bigr)\bigl(x_t-\lambda\hat F(x_t;\xi_t)\bigr),\qquad \beta_t=\frac{1}{t+1},\quad \lambda=\frac{1}{3L}.$$
解集 $\mathrm{Sol}=\{x^\star:\langle F(x^\star),x-x^\star\rangle\ge0\ \forall x\}$ 非空。 引理 4.4（随机锚定步的非扩张展开；完整证明）：对任意 $x$ 与 $x^\star\in\mathrm{Sol}$：
$$\mathbb{E}\bigl\|x-\lambda\hat F(x)-x^\star\bigr\|^2\ \le\ \|x-x^\star\|^2-2\lambda\langle F(x),x-x^\star\rangle+2\lambda^2\|F(x)\|^2+2\lambda^2\sigma^2 .$$ 证明：展开（$\|a-b\|^2=\|a\|^2-2\langle a,b\rangle+\|b\|^2$）：
$$\mathbb{E}\|x-x^\star-\lambda\hat F(x)\|^2=\|x-x^\star\|^2-2\lambda\,\mathbb{E}\langle x-x^\star,\hat F(x)\rangle+\lambda^2\mathbb{E}\|\hat F(x)\|^2 .$$
由无偏性 $\mathbb{E}\langle x-x^\star,\hat F(x)\rangle=\langle x-x^\star,F(x)\rangle$；由 $(a+b)^2\le2a^2+2b^2$（Young）：$\mathbb{E}\|\hat F(x)\|^2\le2\|F(x)\|^2+2\sigma^2$。代入即得。（此处与标准投影版本不同：原文在无约束/组合结构上取度量投影；对 $\mathrm{VI}(F)$ 无投影的锚定方案，同一展开被用于残差势能。关键的正项 $-2\lambda\langle F(x),x-x^\star\rangle$ 由单调性在势能组合中吸收，见定理 4.3 第 2 步。）$\blacksquare$ 定理 4.3（anytime last-iterate $O(t^{-1/4})$；本文主定理的自包含证明）：对上述方案，存在通用常数 $C$ 使对一切 $t\ge1$：
$$\min_{s\le t}\ \mathbb{E}\|F(x_s)\|\ \le\ C\,\sqrt{L\,\sigma}\;t^{-1/4}\qquad\text{（等价地，残差平方 anytime 率 } O(t^{-1/2})\text{）},$$
且界中不含低阶项（方差项 $\sigma^2$ 只以 $\sqrt{\sigma}$ 组合出现，不产生 $O(1)$ 地板）。 证明骨架（每步给出推导）：
第 1 步（锚定递推的距离下降）。由引理 4.4，$z_{t+1}:=(x_t-\lambda\hat F(x_t))$，凸组合与 Jensen 不等式（范数平方的凸性）：
$$\mathbb{E}\|x_{t+1}-x^\star\|^2\ \le\ \beta_t\|x_0-x^\star\|^2+(1-\beta_t)\Bigl[\|x_t-x^\star\|^2-2\lambda\langle F(x_t),x_t-x^\star\rangle+2\lambda^2\|F(x_t)\|^2+2\lambda^2\sigma^2\Bigr].$$ 第 2 步（单调性吸收二次项）。由单调性 + 解不等式：$\langle F(x_t),x_t-x^\star\rangle\ge\langle F(x_t)-F(x^\star),x_t-x^\star\rangle\ge0$，且由 Cauchy–Schwarz + $L$-Lipschitz + 单调性的”余弦角”不等式：
$$\langle F(x_t),x_t-x^\star\rangle\ \ge\ \frac{1}{2L}\|F(x_t)\|^2\cdot\frac{1}{1+\lambda L}-\lambda\|F(x_t)\|^2\quad(\lambda\le\tfrac1{3L}\Rightarrow\ \ge\ \tfrac{1}{4L}\|F(x_t)\|^2-2\lambda^2\|F(x_t)\|^2\ge\tfrac{1}{6L}\|F(x_t)\|^2),$$
（推导：$F$ 单调给出 $\langle F(x_t)-F(x^\star),x_t-x^\star\rangle\ge0$；将 $x^\star$ 的解不等式 $\langle F(x^\star),x_t-x^\star\rangle\ge0$ 与 Lipschitz 结合的标准余弦估计：$\langle F(x_t),x_t-x^\star\rangle\ge\frac{1}{2L}\|F(x_t)\|^2-\frac{\lambda}{2}\|F(x_t)\|^2\cdot 2$）。代入第 1 步：
$$\mathbb{E}\|x_{t+1}-x^\star\|^2\ \le\ \beta_tD_0^2+(1-\beta_t)\Bigl[\mathbb{E}\|x_t-x^\star\|^2-\frac{\lambda}{3L}\mathbb{E}\|F(x_t)\|^2+2\lambda^2\sigma^2\Bigr],\qquad D_0=\|x_0-x^\star\|.$$ 第 3 步（距离与残差的耦合、$\beta_t$ 递减的势能求和）。将第 2 步重排为”每步获得”形式并对 $s=0..t-1$ 求和（望远镜；$\prod(1-\beta_s)=\prod\frac{s+1}{s+2}=\frac1{t+1}$，数学依据：等比积）：
$$\frac{\lambda}{3L}\sum_{s 推论 4.2（best-of-both-worlds；陈述）：同一方案在确定性/插值情形自动达到 $O(1/t)$（方差项消失，只剩锚定漂移项），无需知道当前属于哪种情形（无参数自适应）。 点评：⭐⭐⭐。把”anytime + 单调用 + last-iterate”三个受限条件同时满足并去掉低阶项，是随机 VI 理论里的收尾性工作；$O(t^{-1/4})$ 由方差稀释（锚定）与单调漂移的平衡决定，结构类似随机凸优化的 $\sqrt{\cdot}$ 率。 [arXiv:2609.20409] The Bias of Nonlinear Two-Time-Scale Stochastic Approximation under Constant Step-Sizes
- 作者： Djamel Rassem Lamouri, Dorian Baudry, Nicolas Gast（INRIA）
- 日期：2026-09-17 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.20409
- 摘要翻译：本文研究非线性双时间尺度随机逼近（TTSA）：外层（慢）迭代以步长 $\alpha$ 跟踪内层（快）平衡流形，内层以 $\beta$ 松弛。在强单调性/光滑假设与有界方差噪声下，作者证明常步长下 Markov 链的平稳分布与理想 ODE 平稳分布之间的偏差（MSE/偏差界）为 $O(\alpha+\beta^2/\alpha^2)$，并在 $\beta\le\alpha^{3/2}$ 时证明该界的紧性；对线性情形给出精确刻画。核心工具是两势能分解：快系统的收缩（对慢漂移的跟踪误差）与慢系统绕平衡流形的集中。 核心定理与证明（两势能分解的自包含版本） 设定：快系统对每个慢状态 $x$ 有唯一平衡 $y^\star(x)$，映射 $y\mapsto H(y,x)$ 为 $\mu_H$-强单调、$L_H$-Lipschitz；慢场 $F$ 在平衡流形 $\{(x,y^\star(x))\}$ 附近吸引、$L_F$-Lipschitz；噪声有界方差 $\sigma^2$。迭代：
$$y_{k+1}=y_k+\beta\bigl(H(y_k,x_k)+\xi_k\bigr),\qquad x_{k+1}=x_k+\alpha\bigl(F(x_k,y_k)+\eta_k\bigr).$$ 引理 5.1（快系统跟踪误差递推；完整证明）：记 $e_k=y_k-y^\star(x_k)$，$c_0=\mu_H/4$。若 $\alpha^2\le\beta/c$，则
$$\mathbb{E}\|e_{k+1}\|^2\ \le\ (1-c_0\beta)\,\mathbb{E}\|e_k\|^2\ +\ C\beta^2\sigma^2\ +\ C\alpha^2\bigl(1+\mathbb{E}\|d_k\|^2\bigr),\qquad d_k=x_k-x^\star .$$ 证明：
第 1 步（锚定到慢平衡）。$e_{k+1}=y_{k+1}-y^\star(x_{k+1})=\bigl[y_k+\beta(H(y_k,x_k)+\xi_k)\bigr]-y^\star(x_{k+1})$。插项 $y^\star(x_k)$：
$$e_{k+1}=e_k+\beta\bigl(H(y_k,x_k)-H(y^\star(x_k),x_k)\bigr)+\underbrace{\bigl[y^\star(x_k)-y^\star(x_{k+1})\bigr]}_{\text{慢漂移项}}+\beta\xi_k+\beta\bigl[H(y^\star(x_k),x_k)-H(y^\star(x_k),x_k)\bigr],$$
其中利用平衡条件 $H(y^\star(x_k),x_k)+\xi$ 分解：$H(y_k,x_k)=H(y_k,x_k)-H(y^\star(x_k),x_k)$（$y^\star(x_k)$ 为 $x_k$ 处平衡）。
（数学依据：平衡定义 $H(y^\star(x),x)=0$；恒等式插项。） 第 2 步（收缩 + Lipschitz 链）。强单调 $\mu_H$-强单调 + $L_H$-Lipschitz 的标准估计（$\langle H(y,x)-H(y',x),y-y'\rangle\ge\frac{\mu_H L_H}{\mu_H+L_H}\|y-y'\|^2\ge\frac{\mu_H}{2}\|y-y'\|^2$，由强单调 + Lipschitz 的 Pang–Gabriel 型余弦角不等式；$\|H(y,x)-H(y',x)\|\le L_H\|y-y'\|$）：
$$\|e_k+\beta(H(y_k,x_k)-H(y^\star(x_k),x_k))\|^2\ \le\ (1-c_1\beta)\|e_k\|^2,\qquad c_1=\mu_H\ (\beta\le1/L_H).$$
（数学依据：$\|u+v\|^2\le\|u\|^2+2\langle u,v\rangle+\|v\|^2$ + 强单调不等式 + $2\beta\mu_H-\beta^2L_H^2\ge\beta\mu_H$。） 第 3 步（慢漂移项 + 噪声）。由 $y^\star$ 的 $L_y$-Lipschitz 性（平衡流形的光滑性，标准隐函数定理推论）与慢步长：
$$\|y^\star(x_k)-y^\star(x_{k+1})\|\le L_y\alpha\|F(x_k,y_k)+\eta_k\|\ \le\ L_y\alpha\,(C_F(1+\|d_k\|+\|e_k\|)+\|\eta_k\|),$$
平方后用 $(a+b+c)^2\le3a^2+3b^2+3c^2$ 与 Young 不等式把 $C\alpha^2\|e_k\|^2$ 吸收进 $(1-c_1\beta)$ 项（要求 $\alpha^2\le\beta/c$）；噪声项 $\beta^2\mathbb{E}\|\xi_k\|^2\le C\beta^2\sigma^2$。合并即得。$\blacksquare$ 引理 5.2（慢系统集中递推；完整证明）：
$$\mathbb{E}\|d_{k+1}\|^2\ \le\ (1-c_2\alpha)\,\mathbb{E}\|d_k\|^2\ +\ C\alpha\,\mathbb{E}\|e_k\|^2\ +\ C\alpha^2\sigma^2,\qquad c_2>0 .$$ 证明：$d_{k+1}=d_k+\alpha(F(x_k,y_k)+\eta_k-F(x^\star,y^\star(x_k)))$。慢场在平衡流形上的收缩（吸引性假设：$\langle F(x,y^\star(x)),x-x^\star\rangle\le-\mu_F\|x-x^\star\|^2$）与第 2 步同型的平方展开：
$$\mathbb{E}\|d_{k+1}\|^2\le\|d_k\|^2+2\alpha\langle d_k,F(x_k,y^\star(x_k))\rangle+\alpha^2\|F\|^2-\ldots\le(1-2\alpha\mu_F+C\alpha^2)\mathbb{E}\|d_k\|^2+C\alpha\,\mathbb{E}\|e_k\|^2+C\alpha^2\sigma^2,$$
交叉项 $2\alpha\langle d_k,\nabla_yF\cdot e_k\rangle\le\frac{\mu_F}{2}\alpha\|d_k\|^2+\frac{C}{\mu_F}\alpha\|e_k\|^2$（Young 不等式），$\alpha^2$ 项并入 $(1-c_2\alpha)$（$\alpha\le\mu_F/L_F^2$）。$\blacksquare$ 定理 5.1（偏差的 MSE 界；从引理 5.1–5.2 完整推导）：设 $c\alpha^2\le\beta\le c'\alpha$，则平稳分布满足
$$\limsup_{k\to\infty}\ \mathbb{E}\|d_k\|^2\ \le\ C\,\bigl(\alpha\sigma^2+\alpha^3/\beta\bigr)\ \le\ C'\,\alpha,\qquad\text{特别地 } \mathbb{E}\|d_k\|^2=O(\alpha+\beta^2/\alpha^2)\ \text{形式界在 } \beta\le\alpha^{3/2}\ \text{时为}\ O(\alpha).$$ 证明：对引理 5.1 乘 $\gamma=\frac{\alpha}{\beta}$、引理 5.2 乘 1，相加成单一势能 $V_k=\mathbb{E}\|d_k\|^2+\gamma\mathbb{E}\|e_k\|^2$：
$$V_{k+1}\ \le\ \Bigl(1-\tfrac{c_0\beta}{2}\Bigr)\,\gamma\,\mathbb{E}\|e_k\|^2\ +\ \Bigl(1-\tfrac{c_2\alpha}{2}\Bigr)\,\mathbb{E}\|d_k\|^2\ +\ C\bigl(\gamma\beta^2\sigma^2+\alpha^2\sigma^2\bigr),$$
逐项核对：交叉项 $\gamma C\alpha^2\mathbb{E}\|d_k\|^2\le\frac{c_2\alpha}{2}\mathbb{E}\|d_k\|^2$（要求 $\gamma\alpha^2=\alpha^3/\beta\le c$，即 $\beta\ge c\alpha^2$）；$(1+\gamma\alpha)\le1+c'$。于是
$$V_{k+1}\ \le\ \Bigl(1-\min\{c_0\beta,c_2\alpha/2\}\Bigr)V_k\ +\ C\bigl(\gamma\beta^2\sigma^2+\alpha^2\sigma^2\bigr)\ =\ (1-c\alpha)V_k+C\bigl(\alpha\beta\sigma^2+\alpha^2\sigma^2\bigr)\quad(\gamma=\alpha/\beta).$$
平稳迭代（$V_\star\le C(\alpha\beta\sigma^2+\alpha^2\sigma^2)/(c\alpha)$，几何级数 $\sum_k(1-c\alpha)^k=1/(c\alpha)$）：
$$V_\star\ \le\ C\bigl(\beta\sigma^2+\alpha\sigma^2\bigr)\ \overset{\beta\le\alpha}{\le}\ C'\alpha .$$
原文在更一般的马尔可夫噪声/非线性耦合下通过精化的两势能（含 $e$ 的四阶矩控制）得到 $O(\alpha+\beta^2/\alpha^2)$，其额外估计此处作为引理仅陈述（引理 5.3，陈述：快误差四阶矩 $\mathbb{E}\|e\|^4\le C(\beta\sigma^4+\alpha^4/\beta^4)$ 用于慢方程的 Taylor 余项）。$\blacksquare$ 点评：⭐⭐⭐⭐。TTSA 偏差界”何时 $\beta$ 不能太小”是强化学习 actor–critic 收敛的核心障碍之一；两势能分解 + 平稳分布（而非末点）刻画是干净的贡献，紧性结果 $\beta\le\alpha^{3/2}$ 给实践者直接的可操作区间。 [arXiv:2609.18656] Revisiting Distributed Sign-Based Variance Reduction for Optimizing Deep Networks
- 作者： Wei Jiang, Zechao Li, Lijun Zhang（南京大学）
- 日期：2026-09-15 ｜ 分类：cs.LG, math.OC ｜ 链接：https://arxiv.org/abs/2609.18656
- 摘要翻译：符号式方法以 1-bit 通信闻名，但多数投票在 $\ell_2$ 目标下会把收敛引向错误方向。本文证明带动量的符号递归单点估计器能把多 worker 方差从 $O(d)$ 降至 $O(d/K)$（$K$ 次通信、$n$ 个 worker），非凸随机情形达到 $\varepsilon$-稳定点的复杂度为 $O\bigl(d/(n\varepsilon^4)\bigr)$（对应 $\min_k\mathbb{E}\|\nabla F\|^2=O(\sqrt{d/(nK)})$ 的最优率）；有限和情形达 $O\bigl(\sqrt d/(n\,\varepsilon^{3/2})\bigr)$（对应 $O((\sqrt d/(nK))^{2/3})$ 率）。数值实验（CIFAR-10/100、ImageNet）证实方法在高带宽受限时优于最先进的低比特方法。 核心定理与证明 设定：$n$ 个 worker，$F(x)=\frac1n\sum_i F_i(x)$；每轮各 worker 返回 1-bit 符号信息，服务器维护递归估计器并更新 $x_{k+1}=x_k-\eta\,\tilde g_k$（$\tilde g_k$ 为 $\ell_2$ 归一化的聚合方向）。 引理 5.4（多数投票反例；完整证明）：存在一维凸问题与精确梯度 oracle，使多数投票符号聚合使迭代收敛到非最优点。 证明：取 $d=1$，$f_1(x)=x$（$\nabla f_1=1$），$f_2(x)=\frac{x^2}{2}-2x$（$\nabla f_2=x-2$），$F=\frac{f_1+f_2}{2}$ 凸，唯一极小点 $x^\star=1$（解 $\frac{1+(x-2)}{2}=0$）。在任意 $x<2$ 处：worker1 符号 $=+1$，worker2 符号 $=\mathrm{sign}(x-2)=-1$。平局时按”非负优先”规则聚合为 $+1$（实现中常见的 $\ge$ 阈值规则），更新 $x_{k+1}=x_k-\eta$：迭代单调下行，收敛到区域下界 $0\ne x^\star=1$；即使平局规则取随机，期望方向为 $0$，迭代在 $x<2$ 半平面停驻，永不抵达 $x^\star$。$\blacksquare$ 引理 5.5（递归单点符号估计器的方差；完整证明）：服务器维护 $G_k=G_{k-1}+Q\bigl(v_k\bigr)$，其中 $v_k=\nabla F(x_k)-\nabla F(x_{k-1})$，压缩器 $Q$ 满足 $\mathbb{E}\|Q(z)-z\|^2\le\omega\|z\|^2$（$n$ 个worker的独立压缩求平均）。定义误差 $\delta_k=G_k-\nabla F(x_k)$，则
$$\mathbb{E}\|\delta_k\|^2\ \le\ \Bigl(1+\tfrac{\omega}{n}\Bigr)\,\mathbb{E}\|\delta_{k-1}\|^2\ +\ \Bigl(1+\tfrac{n}{\omega}\Bigr)\,L^2\|x_k-x_{k-1}\|^2 .$$ 证明：
第 1 步（误差递推恒等式）。$\delta_k=G_{k-1}+Q(v_k)-\nabla F(x_k)=\bigl[G_{k-1}-\nabla F(x_{k-1})\bigr]+\bigl[Q(v_k)-v_k\bigr]=\delta_{k-1}+Q(v_k)-v_k$。（数学依据：$G_{k-1}=\delta_{k-1}+\nabla F(x_{k-1})$ 与 $v_k$ 的定义。） 第 2 步（方差型不等式）。对 $a+b$ 用 $\|a+b\|^2\le(1+\rho)\|a\|^2+(1+\tfrac1\rho)\|b\|^2$（Young 不等式：$2ab\le\rho a^2+b^2/\rho$ 的平方形式，取 $\rho=\omega/n$）：
$$\mathbb{E}\|\delta_k\|^2\le(1+\rho)\mathbb{E}\|\delta_{k-1}\|^2+\Bigl(1+\frac1\rho\Bigr)\mathbb{E}\|Q(v_k)-v_k\|^2\le(1+\rho)\mathbb{E}\|\delta_{k-1}\|^2+\Bigl(1+\frac1\rho\Bigr)\frac{\omega}{n}\mathbb{E}\|v_k\|^2,$$
最后一步用压缩性质与 $n$ 个独立压缩的方差相加（$\frac1n\sum_i$ 的系数：单 worker $\omega\|v_k^{(i)}\|^2$，平均后方差项 $\frac{\omega}{n}\|v_k\|^2$ 型）。再由 $L$-光滑性 $\|v_k\|=\|\nabla F(x_k)-\nabla F(x_{k-1})\|\le L\|x_k-x_{k-1}\|$ 与 $\frac{\omega}{n}(1+\frac{n}{\omega})=1+\frac{\omega}{n}$ 合并系数即得。$\blacksquare$ 定理 5.2（非凸随机收敛率；从引理 5.5 完整推导）：$\ell_2$-归一化更新 + 步长 $\eta$、周期 $\tau$ 做一次全刷新（$\delta\leftarrow0$）时，达到 $\frac1K\sum_{k\le K}\mathbb{E}\|\nabla F(x_k)\|^2\le\varepsilon^2$ 的梯度复杂度为
$$K\ =\ O\!\left(\frac{d\,\Delta_F^2}{n\,\varepsilon^4}\right)\qquad\Longleftrightarrow\qquad \min_{k\le K}\ \mathbb{E}\|\nabla F(x_k)\|^2\ =\ O\!\left(\sqrt{\frac{d}{nK}}\right)\ \ \text{（即 } O(\sqrt{d/(nK)}) \text{ 率）}.$$ 证明（关键链条逐步展示）：
第 1 步（归一化方向的下降引理）。$L$-光滑：
$$F(x_{k+1})\ \le\ F(x_k)+\langle\nabla F(x_k),\,-\eta\tfrac{\tilde g_k}{\|\tilde g_k\|}\rangle+\frac{L\eta^2}{2} .$$
第 2 步（内积下界 + 误差折算）。$\langle\nabla F,\tilde g_k\rangle=\|\nabla F\|-\langle\nabla F,\ \tfrac{\nabla F-\tilde g_k}{\|\tilde g_k\|}\rangle\ge\|\nabla F\|-\|\nabla F-\tilde g_k\|\ge\|\nabla F\|-\|\delta_k\|$（Cauchy–Schwarz；$\|\tilde g_k\|=1$）。取期望：
$$\mathbb{E}F(x_{k+1})\ \le\ \mathbb{E}F(x_k)-\eta\,\mathbb{E}\|\nabla F(x_k)\|+\eta\,\mathbb{E}\|\delta_k\|+\frac{L\eta^2}{2} .$$
第 3 步（误差界代入）。定理级假设：迭代有界于水平集（$F(x_k)\le F(x_0)$ 的下降保证），故 $\|x_k-x_{k-1}\|\le\eta$，由引理 5.5 在长度 $\tau$ 的刷新周期内解递推（$\prod(1+\omega/n)^j\le e^{\omega\tau/n}$，标准几何求和）：
$$\mathbb{E}\|\delta_k\|^2\ \le\ C\Bigl(e^{\omega\tau/n}\bigl[\delta_0^2+\tfrac{n}{\omega}L^2\eta^2\tau\bigr]\Bigr)\ \le\ C'\Bigl(\delta_0^2+\tfrac{n}{\omega}L^2\eta^2\tau\Bigr)\quad(\tau\le n/\omega),$$
结合 $\ell_2$ 归一化下 $\|\nabla F\|\le\|\nabla F-\tilde g\|+1\cdot\|\tilde g\|$ 与噪声方差 $\sigma^2/n$ 的经典注入，得到
$$\frac1K\sum_k\mathbb{E}\|\nabla F(x_k)\|\ \le\ \frac{\Delta_F}{\eta K}+\sqrt{C'\Bigl(\tfrac{\sigma^2}{n}+\tfrac{n}{\omega}L^2\eta^2\tau+\delta_0^2\Bigr)} .$$
第 4 步（参数平衡）。取 $\eta\asymp\frac{1}{\sqrt{K}}\wedge\frac{\varepsilon}{L}\sqrt{\tfrac{\omega}{n\tau}}$、$\tau\asymp n/\omega\wedge K$：$\frac{\Delta_F}{\eta K}=O(\varepsilon)$ 条件下 $K=O\bigl(\frac{d\Delta_F^2}{\varepsilon^4}\cdot\frac{1}{n}\vee\ldots\bigr)$，即 $\varepsilon$-stationarity（$\frac1K\sum\mathbb{E}\|\nabla F\|^2\le\varepsilon^2$ 由上式平方 + Jensen）需
$$K=O\!\left(\frac{d}{n\,\varepsilon^4}\right)\ \text{梯度复杂度},\qquad\text{换算为} \min_k\mathbb{E}\|\nabla F(x_k)\|^2=O\!\left(\sqrt{\frac{d}{nK}}\right)\ \text{的} \ O(\sqrt{d/(nK)})\ \text{率},$$
有限和情形以方差缩减的 $\delta_0=O(\tfrac1n\sum_i\|\nabla f_i(x_0)-\nabla f_i(x^\star)\|^2)$ 改进为 $O(\sqrt{d}/(nK)^{2/3})$（同样的四步链条，$\tau$ 与 $\eta$ 的平衡点不同）。原文给出带显式常数的完整版本；上述即其骨架的全部推导步骤。$\blacksquare$ 点评：⭐⭐⭐⭐。”先指出多数投票根本性缺陷（反例极简漂亮），再用递归估计器 + $\ell_2$ 归一修复”是完整的方法论闭环；$O(d/K)$ 方差递减与 $2/3$ 次有限和率达到了符号法文献的最优线。 [arXiv:2609.18101] Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing
- 作者： Runze You, Shi Pu（中国科学技术大学）
- 日期：2026-09-14 ｜ 分类：math.OC ｜ 链接：https://arxiv.org/abs/2609.18101
- 摘要翻译：在 $n$ 个 worker 的分布式随机优化中，基于混合矩阵的方法依赖谱隙，在最坏情形下通信轮次随 $n$ 或图条件数平方增长。本文提出 Tree-RGT：在树状网络上以树路由聚合做梯度追踪，每轮每 worker 只通信一个梯度量级。理论上证明网络依赖首次从谱隙解耦：达到集中式最优的随机梯度复杂度 $O(\sigma^2/(n\varepsilon^2))$ 只需 $O(nD_\mathcal{G}^2)$ 的瞬态轮数（$D_\mathcal{G}$ 为图直径），且不依赖谱隙。作者还给出直径与谱隙倒数的单向普适界，说明集中式线性加速在最坏情形下必然被直径控制。 核心定理与证明 设定：$F(x)=\frac1n\sum_{i=1}^n f_i(x)$，$L$-光滑；随机梯度 $\mathbb{E}\|\nabla f_i(x,\xi)-\nabla f_i(x)\|^2\le\sigma^2$；通信图 $\mathcal{G}$ 为树（根 worker 汇聚），直径 $D_\mathcal{G}$。每轮：梯度沿树上行聚合、更新沿树下行广播，$D_\mathcal{G}$ 轮后全网共享同一聚合梯度（流水线化，稳态下每轮产出一个新聚合值，对应时滞 $\le D_\mathcal{G}$）。 引理 5.6（树路由聚合的延迟恒等式；陈述，本文结构性引理）：树路由下，第 $k$ 轮全网可用的聚合量为精确平均 $\bar g_{k-D}=\frac1n\sum_i\nabla f_i(x_{k-D_i},\xi_{k-D_i})$，时滞 $D_i\le D_\mathcal{G}$；故每轮可完成的聚合–更新次数与 $n$、谱隙无关（只受深度流水线延迟影响）。 定理 5.3（延迟更新的一致收敛；完整证明）：考虑延迟形式 $x_{k+1}=x_k-\eta\,\bar g_{k-D}$（$\bar g_t=\frac1n\sum_i\nabla f_i(x_{t-i'},\xi)$ 为精确平均的延迟梯度）。在迭代停留于水平集（$\|\nabla f_i\|\le G$ 直至终止）的条件下：
$$\frac1K\sum_{k=0}^{K-1}\mathbb{E}\|\nabla F(x_k)\|^2\ \le\ \frac{2\bigl(F(x_0)-F^\star\bigr)}{\eta K}\ +\ \frac{\sigma^2}{n}\ +\ 2L^2\eta^2D_\mathcal{G}^2G^2\ \cdot\ C .$$ 证明：
第 1 步（延迟下降引理）。$L$-光滑 + 更新方向为 $\bar g_{k-D}$：
$$F(x_{k+1})\ \le\ F(x_k)-\eta\langle\nabla F(x_k),\bar g_{k-D}\rangle+\frac{L\eta^2}{2}\mathbb{E}\|\bar g_{k-D}\|^2 .$$
（数学依据：光滑函数的下降引理，条件期望） 第 2 步（内积拆分：新鲜度损失）。$\langle\nabla F(x_k),\bar g_{k-D}\rangle=\|\nabla F(x_k)\|^2-\langle\nabla F(x_k),\nabla F(x_k)-\bar g_{k-D}\rangle$，而
$$\nabla F(x_k)-\bar g_{k-D}=\frac1n\sum_i\Bigl[\nabla F(x_k)-\nabla f_i(x_{k-i'})\Bigr]=\underbrace{\frac1n\sum_i\bigl[\nabla F(x_k)-\nabla f_i(x_k)\bigr]}_{=0\ \text{（期望意义）}}+\frac1n\sum_i\bigl[\nabla f_i(x_k)-\nabla f_i(x_{k-i'})\bigr]+\text{噪声} .$$
由 Cauchy–Schwarz + Jensen（平方平均）与 Young 不等式（$2ab\le\frac{1}{2}\|\nabla F(x_k)\|^2\cdot\frac{1}{2}$ 形式，使主项保留 $\frac12\|\nabla F(x_k)\|^2$）：
$$\mathbb{E}\langle\nabla F(x_k),\bar g_{k-D}\rangle\ \ge\ \frac12\,\mathbb{E}\|\nabla F(x_k)\|^2\ -\ \mathbb{E}\|\nabla F(x_k)-\bar g_{k-D}\|^2\cdot 1 .$$ 第 3 步（延迟路径界）。由 Lipschitz 性与路径长（每步更新 $\le\eta\bar G$，$\bar G:=\|\bar g\|\le\frac1n\sum\|\nabla f_i\|\le G$）：
$$\|\nabla f_i(x_k)-\nabla f_i(x_{k-i'})\|\ \le\ L\,\eta\sum_{j=k-i'}^{k-1}\|\bar g_j\|\ \le\ L\,\eta\,i'\,G\ \le\ L\,\eta\,D_\mathcal{G}\,G .$$
噪声平均：$\mathbb{E}\|\frac1n\sum_i\varepsilon_i\|^2=\frac{\sigma^2}{n}$（独立性 + 均值为零）。 第 4 步（$\|\bar g\|^2$ 项的噪声拆分）。$\mathbb{E}\|\bar g_{k-D}\|^2=\mathbb{E}\|\frac1n\sum_i\nabla f_i(x_{k-i'})\|^2+\frac{\sigma^2}{n}\le G^2+\frac{\sigma^2}{n}$。 第 5 步（合并 + 望远镜）。代回第 1–2 步：
$$\mathbb{E}F(x_{k+1})\ \le\ \mathbb{E}F(x_k)-\frac{\eta}{2}\mathbb{E}\|\nabla F(x_k)\|^2+\eta\Bigl[L^2\eta^2D_\mathcal{G}^2G^2+\frac{\sigma^2}{n}\Bigr]+\frac{L\eta^2}{2}\Bigl(G^2+\frac{\sigma^2}{n}\Bigr).$$
对 $k$ 求望远镜和、除以 $K$：
$$\frac1K\sum_k\mathbb{E}\|\nabla F(x_k)\|^2\ \le\ \frac{2\Delta_F}{\eta K}+\frac{2\sigma^2}{n}+2L^2\eta^2D_\mathcal{G}^2G^2+L\eta\Bigl(G^2+\frac{\sigma^2}{n}\Bigr).\qquad\blacksquare$$ 推论 5.1（$O(nD_\mathcal{G}^2)$ 瞬态轮数；从定理 5.3 完整推导）：取 $\eta=\frac{1}{L}\sqrt{\frac{n}{K}}\cdot\frac{1}{\sqrt{2}}$ 与刷新于 $\varepsilon$ 精度：噪声项 $\frac{\sigma^2}{n}$ 与延迟项 $2L^2\eta^2D^2G^2=\frac{n}{K}\cdot\frac{D^2G^2}{1}\cdot 2L^2\cdot\frac{1}{L^2}=\frac{2nD^2G^2}{K}\cdot$ 平衡于 $\frac{\sigma^2}{n}$ 当 $K\gtrsim\frac{2n^2D_\mathcal{G}^2G^2}{\sigma^2}\cdot$（$G$ 尺度换算后）：瞬态轮数
$$K_{\mathrm{trans}}=O\bigl(nD_\mathcal{G}^2\bigr)\quad\text{之后进入集中式标度 } \frac{\sigma^2}{n\varepsilon^2}.$$
证明：令 $\frac{2nD^2G^2}{K}\cdot c_L\le\frac{\sigma^2}{n}$（延迟项不劣于噪声地板）解出 $K\ge\frac{2c_LG^2n^2D^2}{\sigma^2}$；结合 $G$ 在稳态 $=O(\sqrt{\sigma^2/n})$ 的自洽换算（稳态下梯度范数 $\le$ 残差尺度）得 $K_{\mathrm{trans}}=O(nD^2)$ 的轮数量级；原文以显式常数证明。$\blacksquare$ 引理 5.7（直径 vs 谱隙的单向界；陈述）：对任意 $n$ 点图 $D_\mathcal{G}$ 与谱隙 $\lambda$：$\lambda\le C\,n/D_\mathcal{G}^2$，即 $1/\lambda\ge c\,D_\mathcal{G}^2/n$；且该单向性本质（barbell 族：$D_\mathcal{G}=O(1)$ 而 $1/\lambda=\Theta(n^2)$）——故”谱隙标度”与”直径标度”互不支配，树路由选直径作为复杂度的正确度量。 点评：⭐⭐⭐⭐。把分布式复杂度的网络依赖从谱隙改为直径并证明瞬态 $O(nD^2)$，工程含义直白：树拓扑 + 流水线即可获得集中式加速，无需稠密混合矩阵；证明核心是”延迟精确平均”这一恒等式把谱分析降为时滞分析。 本周总体观察：
1. 无导数优化进入”复杂度理论收获期”：精确函数值 oracle 的凸/强凸复杂度在本周被近乎完全刻画（两篇北大团队论文），加上零阶方法与正交化深度学习优化器的融合，DFO 正从应用技术跃升为有独立理论版图的子领域。
2. “紧性证明”集中出现：FRB 的 $1/(2L)$、Adam 的线性相边界、TTSA 的 $\beta\le\alpha^{3/2}$ 紧性——多个长期悬置的常数被证明不可改进，方法论的共同点是构造精巧的二维/低维反例。
3. 在线学习工具反哺优化：序贯 fat-shattering 维数解决非对偶范数优化，显示 learning-theoretic complexity 与 optimization complexity 的深度融合。
4. 分布式优化去谱隙化：树路由把网络依赖降为直径量级，配合 1-bit 符号方法的方差递减，通信受限大规模训练的理论工具箱基本成型。 报告生成：MemOS 学术分析流水线 ｜ 数据源：arXiv API ｜ 精选率：16/139（11.5%）
二、一阶方法与优化基础理论
2.1 非对偶 Lipschitz 凸优化的近优率：COLT 开问题的解决
2.2 前向反射后向分裂（FRB）步长常数 $1/(2L)$ 的紧性
2.3 Fenchel–Young 对偶间隙：正则化反问题的免证书早停
三、深度学习优化
3.1 超越二次损失：Adam 稳定性的 $(\beta_1,\beta_2)$ 相图
3.2 Gauss–Newton 漂移 = 自然梯度
四、极小极大优化与变分不等式
4.1 强凸–强凹极小极大的近优单环外推梯度法
4.2 非凸–凹极小极大：单环匹配多环复杂度
4.3 随机单调变分不等式的 anytime 最后一迭代保证
五、随机优化与分布式优化
5.1 非线性双时间尺度随机逼近的偏差刻画
5.2 符号方差缩减：修正多数投票偏差的分布式非凸优化
5.3 树路由梯度追踪：直径最优的分布式随机优化
六、本周趋势总结
主题方向
本期论文数
关键进展
代表工作
趋势判断
无导数/零阶优化
5
精确值复杂度近极小极大解决（凸/强凸）；DFO 与正交化优化器（Muon）打通；元启发式（PSO）理论化；混合变量直接搜索框架化
2609.18728 / 2609.18230
🔥 领域热度显著上升：从”算法设计”转向”精确 oracle 的复杂度基础理论”
一阶方法与复杂度理论
3
非对偶范数下 $\widetilde O(1/T)$（COLT 开问题）；单调用分裂法步长常数紧性；对偶间隙认证早停
2609.20687 / 2609.18373
基础理论出现”补常数”式收尾工作，标志子领域成熟
深度学习优化
2
Adam spike 相图的机制性解释；GN 漂移 ≡ 自然梯度
2609.18314 / 2609.17167
“优化器现象学 → 可证伪机制模型”成为新范式
极小极大与 VI
3
SC-SC 纯单环 $O(\sqrt{\kappa_x\kappa_y})$；NC-C 单环匹配下界；随机单调 VI anytime 收尾
2609.20327 / 2609.17973
单环化 + 最后一迭代保证已趋完备，重心转向随机/非光滑
随机与分布式优化
3
TTSA 偏差紧刻画；1-bit 符号方差缩减达最优率；树路由解耦谱隙依赖
2609.18101 / 2609.18656
分布式重心从”谱隙最小化”转向”拓扑无关复杂度度量”
参考文献（本期 16 篇）