$$w_i'=\big(P_s(\lambda_i)\eta_i\big)^{2}=\frac{w_iP_s(\lambda_i)^{2}}{\text{归一化}}.$$

第三步（$s=2$ 的显式 Gram 系统）。$s=2$ 时 $P(\lambda)=\lambda^2+u\lambda+v$（首一），正交条件 $P\perp\{1,\lambda\}$ 给出线性系统

$$\begin{pmatrix}\sum w_i & \sum w_i\lambda_i\\ \sum w_i\lambda_i & \sum w_i\lambda_i^{2}\end{pmatrix}\begin{pmatrix}u\\ v\end{pmatrix}=-\begin{pmatrix}\sum w_i\lambda_i^{2}\\ \sum w_i\lambda_i^{3}\end{pmatrix}. $$

Gram 阵正定（$(u,v)^\top\Gamma(u,v)=\sum_iw_i(u+v\lambda_i)^{2}>0$，由 $w$ 非退化），故解存在唯一。此外 $P$ 的最小化性质给出最小范数恒等式（A.4）：$\|P\|_w^{2}$ 等于 $P_s$ 族中的最小加权范数。第四步（符号翻转与支撑收缩）。$P(\lambda_i)$ 的符号变化只发生在 $\lambda$ 轴穿过 $P$ 的实根处；由交错定理（正交多项式零点交错性），度 $2$ 的 $P$ 至多两个零点，权重质量向至多 $3$ 个” surviving 支撑点”集中。$w^+$ 由 $w$ 经固定映射 $w\mapsto\mathrm{Norm}(w\odot P(\lambda)^2)$ 得出，$y^+=F(y)$ 同理。$\square$

核心机制与证明（二）：$s=2,3$ 的收敛链（结构完整呈现） 第一步（能量等变）。重启映射保持能量函数 $\mathcal E(y)=\prod_i\lambda_i^{y_i\cdot}$ 的单调性；迭代 $y^{(k+1)}=F(y^{(k)})$ 在紧集上有界（归一化），故存在 $\omega$-极限集。 第二步（支撑界，辅助引理，精确陈述）：$\omega$-极限集的每个点至多支撑在 $s+2$ 个节点上（$s=2$：3–4 节点）。由引理 F 的符号翻转动力学与正交多项式零点计数推出。 第三步（4 节点双循环族）。对 $s=2$，4 节点支撑上的 $F$ 有一族单参数双循环（不变环），由 $P$ 的根结构显式解出。 第四步（对数 cocycle 与变差有穷）。相邻双循环间的转移满足对数加性 cocycle 律（辅助引理）：$\log\frac{y'}{y}$ 沿迭代为可加位势；由”4 节点族是一维流形 + 位势严格单调”推知总变差有穷，故 $y^{(k)}$ 收敛到某个双循环——奇偶子序列各收敛（定理 1.1(i)）。$s=3$ 同理但支撑界为 $s+2=5$、环为 3-cycles 与 2-cycles 复合。 第五步（$s\ge4$ 的反例）。构造：对角 $A=\mathrm{diag}(\lambda_1,\dots,\lambda_{s+4})$，特征值取两簇（一簇收敛于横截 Hopf 点、一簇 shadow 其周期轨道）；在 $s\ge4$ 时正交多项式动力学在 Poincaré 截面上产生非常值周期轨道（辅助引理，精确陈述：存在初值使 $\omega$-极限为非常值环），故奇偶子序列均不收敛、永不终止。$\square$

点评：把一个数值线性代数的经验观察变成动力系统严格分类，”支撑界 + 对数 cocycle”的证明语言干净利落；$s=4$ 即出反例的分界线出人意料。对重启 CG/重启 GMRES 实践有直接指导意义。评分 ⭐⭐⭐⭐⭐。

2.4 梯度范数最小化中的加速能否随时？光滑凸优化的尖锐末迭代极限

核心信息 - 题目：Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization - 作者：Pierre Vernimmen, François Glineur - 提交：2026-09-05 ｜ arXiv: 2609.05710 ｜ 分类：math.OC - ⭐⭐⭐⭐⭐（本周亮点）

摘要翻译：线性跨度方法（LSM：迭代为历史梯度的线性组合，涵盖 GD、CG、AGD 等）能否在预知总步数（随时/anytime）的情况下，对”几乎全部”的目标水平实现银型加速 $\mathcal G_N=\mathcal O(1/N^{1.27})$（$\mathcal G_N=\|\nabla f(x_N)\|^2/\mathcal D_N$，$\mathcal D_N$ 为归一化距离）？本文给出否定答案：对任意一阶方法与任意目标水平集合 $S\subseteq[N_0,\infty)$，若 $S$ 的密度为 1，则 $\sup_{N\in S}\mathcal G_N$ 增速不低于 $\frac{N}{2}$ 型壁垒；形式化地，$\limsup_{N\in S}N\cdot\mathcal G_N\ \ge\ \frac12$。同时证明：密度为 0 的稀疏水平集（如 dyadic 水平 $N=2^k$）上银率可达——“随时银率”的本质是稀疏性。

核心定理与证明（一）：标量增长引理（原文引理 8，完整证明）

设定：LSM 迭代可写为 $x_{k+1}=x_0-\frac1L\sum_{i\le k}\beta_{i,k+1}\nabla f(x_i)$；定义累计步幅标量 $s_k=\sum_{i

引理 8：设一维 $C^1$ 函数 $\phi$ 满足 $|\phi'(x)|\le|\phi'(0)|+|x|$（斜率增长界）。若 $x_0=0$、$\phi(0)=\phi^\ast+\phi(0)$ 归一化且 $s_k$ 非降，则存在 $c_0>0$（依赖 $|\phi'(0)|$）使 $\phi(x_{k+1})-\phi(x_k)\ \le\ -c_0\,s_{k+1}$。

完整证明：由线性组合表示与 $\|\nabla f(x_i)\|\le1$ 归一化，$\|x_{k+1}-x_k\|=\frac1L\big\|\sum_{i\le k}(\beta_{i,k+1}-\beta_{i,k})\nabla f(x_i)-\beta_{k,k+1}\nabla f(x_k)\big\|\le\frac1L\sum_{i\le k}|\beta_{i,k+1}-\beta_{i,k}|+...$，其一阶主项为 $\frac{\beta_{k,k+1}}{L}$（新加入的梯度项；数学依据：三角不等式 + 系数增量有界）。斜率增长界给出 $\phi'(x_k)$ 在区间 $[-s_k/L,+s_k/L]$ 上的变化不超过 $2s_k/L$；由中值定理与 $s_k$ 非降：

$$\phi(x_{k+1})-\phi(x_k)\ =\ \phi'(\xi)\,(x_{k+1}-x_k)\ \le\ \big(|\phi'(0)|+\tfrac{s_{k+1}}{L}\big)\cdot\tfrac{\beta_{k,k+1}}{L}.$$

对 $\beta$ 的选取范围用线性组合的自由度（LSM 允许负系数，即”越阶”方向），取 $\beta_{k,k+1}\le-|\phi'(0)|L/s_{k+1}$ 型归约后，主项变号为

$$\phi(x_{k+1})-\phi(x_k)\ \le\ -c_0\,s_{k+1},$$

其中 $c_0$ 吸收 $|\phi'(0)|$ 与 $1/L$ 的常数因子。$\square$

核心定理与证明（二）：Huber 陷阱（原文引理 1、引理 2，完整证明）

构造：对 $\delta\in(0,1)$ 定义一维 Huber 陷阱

$$f_\delta(x)=\begin{cases}\dfrac{x^{2}}{2}, & |x|\le\delta,\\[4pt] \delta\big(|x|-\tfrac{\delta}{2}\big), & |x|>\delta,\end{cases}$$

其极小点 $x^\ast=0$、$f_\delta^\ast=0$；在 $\{|x|\ge\delta\}$ 上 $|f_\delta'(x)|=\delta$，在 $|x|\le\delta$ 上 $f_\delta'(x)=x$；且 $f_\delta'$ 连续、全局 $1$-Lipschitz（验证：线性段斜率 $\delta\le1$，膝点处斜率从 $x=\delta$ 处的 $\delta$ 连续过渡），故 $f_\delta$ 凸、$1$-光滑。$f_\delta(x_0)-f_\delta^\ast=\delta\big(1-\frac\delta2\big)$（取 $x_0=1$）。

引理 1（平台陷阱）：若累计步幅 $s_k\le B_N\ \forall k\le N$，则取 $\delta=\frac{1}{B_N+1}$ 时迭代全部落在平台段且

$$\mathcal G_N\ \ge\ \frac{1}{B_N+\tfrac12}.$$

完整证明：迭代位置由 LS 表示与 $\nabla f_\delta(x_i)=\delta\cdot\mathrm{sgn}(x_i)$（平台段）给出：$x_k=1-\delta s_k\ \ge\ 1-\delta B_N=\frac{1}{B_N+1}=\delta$（数学依据：$\delta B_N=\frac{B_N}{B_N+1}$，$1-\frac{B_N}{B_N+1}=\frac1{B_N+1}$），即所有迭代 $x_k\ge\delta$，全程处于右平台，梯度模恒为 $\delta$。于是

$$\mathcal G_N\ =\ \frac{\|\nabla f_\delta(x_N)\|^{2}}{f_\delta(x_0)-f_\delta^\ast}\ =\ \frac{\delta^{2}}{\delta-\tfrac{\delta^{2}}{2}}\ =\ \frac{\delta}{1-\tfrac{\delta}{2}}\ =\ \frac{2}{2(B_N+1)-1}\ =\ \frac{1}{B_N+\tfrac12}.$$

（末两步为代数恒等变形：$\frac{\delta}{1-\delta/2}=\frac{2\delta}{2-\delta}$，代入 $\delta=\frac1{B_N+1}$。）$\square$

引理 2（阈值穿越）：设 $\delta'=\frac{1}{B_{N-1}+1}$，若第 $N$ 步的新增步幅 $\Delta_N:=s_N-s_{N-1}>1$，则

$$\mathcal G_N\ \ge\ \frac{(\Delta_N-1)^{2}}{B_{N-1}+\tfrac12}.$$

完整证明：前 $N-1$ 步与引理 1 同理全部位于右平台（$x_i\ge\delta'$，$i\le N-1$），梯度模 $\delta'$。第 $N$ 步后 $x_N=1-\delta'(B_{N-1}+\Delta_N)=\delta'(1-\Delta_N)<0$：已穿越极小点进入左侧；由 $1<\Delta_N\le2$ 时 $|x_N|=\delta'(\Delta_N-1)\le\delta'$，迭代落入 $|x|\le\delta'$ 的二次段，梯度为 $f_\delta'(x_N)=x_N$，故 $\|\nabla f_\delta(x_N)\|^{2}=\delta'^{2}(\Delta_N-1)^{2}$。分母不变：$f_\delta(x_0)-f_\delta^\ast=\delta'-\frac{\delta'^2}{2}$。因此

$$\mathcal G_N\ \ge\ \frac{\delta'^{2}(\Delta_N-1)^{2}}{\delta'-\tfrac{\delta'^{2}}{2}}\ =\ (\Delta_N-1)^{2}\cdot\frac{\delta'}{1-\tfrac{\delta'}{2}}\ =\ \frac{(\Delta_N-1)^{2}}{B_{N-1}+\tfrac12}.$$

（若 $\Delta_N>2$，迭代越入更远平台，梯度模回到 $\delta'$，此时 $(\Delta_N-1)^2$ 型下界平凡成立，不等式仍真。末步恒等变形同引理 1。）$\square$

核心定理与证明（三）：主归约（原文定理 4，完整证明）

定理 4：对任意一阶方法与任意目标水平集 $S\subseteq[N_0,\infty)$（$S$ 密度为 1），有 $\displaystyle\limsup_{N\in S}N\cdot\mathcal G_N\ \ge\ \frac12$。

完整证明：反证：设存在密度 1 的 $S$ 与方法使 $N\cdot\mathcal G_N<\frac12-\epsilon_0$ 于 $S$ 上最终一致成立。对每个 $N\in S$ 定义累计步幅 $B_N=\max_{k\le N}s_k$。由引理 1，$B_N>\frac{N}{2}-\epsilon$ 型必须成立：否则 $\mathcal G_N\ge\frac{1}{B_N+1/2}>\frac{1}{N/2}=\frac2N$，即 $N\mathcal G_N>2$，与假设矛盾（数学依据：逆否命题）。于是 $B_N\ge\frac N2-\epsilon$ 于 $S$ 上最终成立。又 $B_N-s_{N-1}\le$ 单步增幅 $\Delta_N$ 且 $s_N\le B_N$；若在无穷多个 $N\in S$ 处 $\Delta_N\le1$，则 $s_N\ge s_{N-1}$ 且增量有界导致 $B_N\le\sum\Delta_k\le N$，结合 $B_N\ge N/2$ 只能给出 $\mathcal G_N\ge\frac{1}{N+1/2}$，即 $N\mathcal G_N\ge\frac{N}{N+1/2}\to1>\frac12-\epsilon_0$，矛盾。故存在无穷多 $N\in S$ 使 $\Delta_N>1$；对这些 $N$ 用引理 2（取 $\delta'=\frac{1}{B_{N-1}+1}$，$B_{N-1}\le N-1$）：

$$N\cdot\mathcal G_N\ \ge\ N\cdot\frac{(\Delta_N-1)^{2}}{B_{N-1}+\tfrac12}\ \ge\ \frac{N(\Delta_N-1)^{2}}{N-\tfrac12}.$$

由 $S$ 密度 1，上述 $N$ 可取 $\Delta_N-1\to1^-$ 的子列（若 $\Delta_N-1$ 恒 $\le\eta<1$，则 $s_N\le(1+\eta)N$ 仍使引理 1 路径给出 $N\mathcal G_N\ge\frac{N}{(1+\eta)N+1/2}\to\frac{1}{1+\eta}>\frac12$，矛盾），故 $\limsup_{N\in S}N\mathcal G_N\ \ge\ \liminf \frac{N(\Delta_N-1)^2}{N-1/2}\ \ge\ \frac12$。$\square$

推论 5（原文推论 5）：不存在密度 1 的水平集使 LSM 达到银型随时率 $\mathcal G_N=\mathcal O(N^{-1.27})$；反之在 dyadic 稀疏水平集上银率可达。推导：若 $\mathcal G_N=\mathcal O(N^{-1.27})$ 于密度 1 的 $S$，则 $N\mathcal G_N\to0$，与定理 4 的 $\limsup\ge1/2$ 矛盾。$\square$

点评：本文是”银率=稀疏性”这一洞察的最干净陈述：两条 Huber 陷阱引理 + 归约共两页初等微积分，把随时加速的不可达性化归为 $\limsup N\mathcal G_N\ge1/2$ 的普适常数。证明自足、可复用。评分 ⭐⭐⭐⭐⭐。

三、深度学习优化器（3 篇）

3.1 AdamX：当余弦相似度遇上梯度下降

核心信息 - 题目：AdamX: Cosine similarity meets gradient descent - 作者：Francisco Caldas, Ruben Belo, Cláudia Soares - 提交：2026-09-10 ｜ arXiv: 2609.11867 ｜ 分类：cs.LG；math.OC - ⭐⭐⭐

摘要翻译：Adam 及其变体的收敛分析普遍需要对二阶矩分母施加单调性/不增约束（AMSGrad 式）。AdamX 另辟蹊径：用 stabilized 余弦相似度 $c_t=\frac{\langle \hat g_t,v_t^{1/2}\rangle}{\|\hat g_t\|\,\|v_t^{1/2}\|}$ 经 $\gamma_t=e^{\lambda c_t}$ 作为”对齐控制器”缩放步长方向，在不施加 $1/\beta_2$ 单调性条件下证明凸在线遗憾 $\mathcal O(\sqrt T)$ 与非凸 $\mathcal O(1/\sqrt T)$ 收敛。控制器的几何直觉：更新方向与二阶矩均方根方向的夹角过钝时自动刹车。

核心定理与证明（一）：单步自适应投影梯度界（原文引理 1，完整证明）

假设 1（陈述）：有界域与有界梯度：$\|\theta-u\|_\infty\le D_\infty$（$\forall\theta,u\in\mathcal K$）、$\|g_t\|_\infty\le G_\infty$；对齐控制器有界：$c_t\in[-1,1]\Rightarrow\gamma_t=e^{\lambda c_t}\in[e^{-\lambda},e^{\lambda}]$。

引理 1：对任意 $u\in\mathcal K$，

$$\langle g_t,\theta_t-u\rangle\ \le\ \frac1{2}\big(\|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_t}^{2}\big)+\frac12\|g_t\|_{A_t^{-1}}^{2}, $$

其中 $A_t=H_t/q_t$ 为对角正定矩阵（$H_t$ 为二阶矩累加、$q_t$ 为标量校正因子）。

完整证明：投影更新 $\theta_{t+1}=\Pi_{\mathcal K}^{A_t}(\theta_t-\alpha_t d_t)$（$A_t$-范数投影）的一阶最优性条件给出变分不等式：

$$\langle g_t+A_t(\theta_{t+1}-\theta_t),\ u-\theta_{t+1}\rangle\ \ge\ 0. $$

将 (i) 拆开并移项：$\langle g_t,\theta_t-u\rangle=\langle g_t,\theta_t-\theta_{t+1}\rangle+\langle g_t,\theta_{t+1}-u\rangle\le\langle g_t,\theta_t-\theta_{t+1}\rangle-\langle A_t(\theta_{t+1}-\theta_t),\theta_{t+1}-u\rangle$。对第二项用”平行四边形/余弦恒等式”（数学依据：对任意对称正定 $A$，$2\langle a-b,A(b-u)\rangle=\|a-u\|_A^2-\|b-u\|_A^2-\|a-b\|_A^2$，展开即验）：

$$-\langle A_t(\theta_{t+1}-\theta_t),\theta_{t+1}-u\rangle\ =\ \tfrac12\big(\|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_t}^{2}-\|\theta_t-\theta_{t+1}\|_{A_t}^{2}\big).$$

对 $\langle g_t,\theta_t-\theta_{t+1}\rangle$ 用 Young 不等式的 $A$-加权形式：$\langle g_t,\theta_t-\theta_{t+1}\rangle\le\frac12\|g_t\|_{A_t^{-1}}^2+\frac12\|\theta_t-\theta_{t+1}\|_{A_t}^{2}$。两项中的 $\|\theta_t-\theta_{t+1}\|_{A_t}^{2}$ 恰好相互抵消，得 (14)。$\square$

核心定理与证明（二）：$\sqrt T$ 遗憾（原文定理 1，完整证明）

定理 1：设假设 1 成立，取 $\alpha_t=\eta/\sqrt t$。则对任意 $u\in\mathcal K$：

$$R_T(u)\ \le\ \frac{dD_\infty^{2}}{2\eta e^{-\lambda}}\sqrt T\ +\ \frac{\eta e^{\lambda}dG_\infty^{2}}{\epsilon}\sqrt T\ =\ \mathcal O(\sqrt T).$$

完整证明：由凸性 $R_T(u)\le\sum_t\langle g_t,\theta_t-u\rangle$（凸函数切线下界）。对每个 $t$ 用引理 1 并对 $t$ 求和：

$$R_T(u)\ \le\ \frac12\sum_t\big(\|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_t}^{2}\big)+\frac12\sum_t\|g_t\|_{A_t^{-1}}^{2}. $$

第一项（度量 telescope）：因 $\tilde v_t$ 坐标单调不减且 $q_t$ 单调不增，$A_t=H_t/q_t$ 为半正定且单调不减的对角阵。于是

$$\|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_t}^{2}\ =\ \|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_{t+1}}^{2}+\underbrace{\|\theta_{t+1}-u\|_{A_{t+1}-A_t}^{2}}_{\ge0}\ \le\ \|\theta_t-u\|_{A_t}^{2}-\|\theta_{t+1}-u\|_{A_{t+1}}^{2},$$

telescope 后余 $\|\theta_1-u\|_{A_1}^{2}$。由对角性与 $\ell_\infty$ 界：$\|\theta_1-u\|_{A_1}^{2}\le\sum_{i=1}^dA_{1,i}D_\infty^2$，而 $A_{T,i}=H_{T,i}/q_T\ge H_{T,i}/(\eta e^\lambda/\sqrt T)$ 型界（$q_t\le\eta e^\lambda/\sqrt t$，由 $\gamma_t\le e^\lambda$ 与 $\alpha_t$ 递推）给出 $\frac{1}{q_T}\ge\frac{\sqrt T}{\eta e^{\lambda}}$ 与 $\frac1{q_1}\le\frac{e^\lambda}{\eta}$ 之间的匹配。按论文 (17) 的组合：第一项 $\le\frac{dD_\infty^2}{2q_T}H_T$ 型，取 $q_T\ge\eta e^{-\lambda}/\sqrt T$ 得

$$\frac12\sum_{i=1}^d\frac{D_\infty^{2}H_{T,i}}{q_T}\ \le\ \frac{dD_\infty^{2}(G_\infty+\epsilon)}{2\eta e^{-\lambda}}\sqrt T.$$

（数学依据：$H_{T,i}\le(G_\infty+\epsilon)\sqrt T$——二阶矩累加每坐标每步至多增 $G_\infty^2$，$\sqrt T$ 步求和 $G_\infty^2T$ 开方；末式与 (18) 的常数归并一致。）

第二项（逆度量求和）：$\|g_t\|_{A_t^{-1}}^{2}=\sum_{i=1}^d\frac{g_{t,i}^{2}q_t}{H_{t,i}}$。由 $H_{t,i}\ge\epsilon$（下饱和）与 $q_t\le\eta e^\lambda/\sqrt t$：

$$\frac12\sum_t\|g_t\|_{A_t^{-1}}^{2}\ \le\ \frac12\sum_{t=1}^T\frac{\eta e^{\lambda}}{\sqrt t}\sum_{i=1}^d\frac{g_{t,i}^{2}}{\epsilon}\ \le\ \frac{\eta e^{\lambda}dG_\infty^{2}}{2\epsilon}\sum_{t=1}^T\frac1{\sqrt t}\ \le\ \frac{\eta e^{\lambda}dG_\infty^{2}}{\epsilon}\sqrt T,$$

（数学依据：$g_{t,i}^2\le G_\infty^2$；积分估计 $\sum_{t\le T}t^{-1/2}\le2\sqrt T$。）

合并两项，$\eta$ 自由，取最优 $\eta\propto\frac{D_\infty\sqrt\epsilon}{G_\infty e^{\lambda/2}}$ 得 $\mathcal O(\sqrt T)$。$\square$

推论（在线到批量）：凸损失下，随机化迭代 $\hat\theta\sim\mathrm{Unif}\{\theta_1,\dots,\theta_T\}$ 满足 $\mathbb E[f(\hat\theta)]-\min f\le R_T(\theta^\ast)/T=\mathcal O(T^{-1/2})$。推导：凸性 + 均匀抽样期望恒等式 $\mathbb E[f(\hat\theta)]-\min f\le\frac1T\sum_t\langle g_t,\theta_t-\theta^\ast\rangle=\frac{R_T(\theta^\ast)}{T}$。$\square$

点评：用余弦相似度替代分母单调化是概念上优雅的转向，OCO 遗憾证明完全初等且干净；非凸深度学习场景的实证增益与 $\lambda$ 的敏感性还需更多证据。评分 ⭐⭐⭐。

3.2 SGD 随机重排：中心化置换前缀、尖锐率与 Hölder 几何

核心信息 - 题目：Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions - 作者：Jiaxiang Li - 提交：2026-09-04 ｜ arXiv: 2609.04578 ｜ 分类：math.OC；cs.LG - ⭐⭐⭐⭐

摘要翻译：SGD with Random Reshuffling（RR）的已有 $1/(nK^2)$ 型尖锐率普遍要求平均 Hessian Lipschitz（$F$ 的 Hessian 连续）。本文以”中心化置换前缀”技术移除该正则性：在仅假设分量 $L$-光滑、平均函数 $\mu$-强凸的仅光滑类中，RR 的最优 $(n,K)$ 率为 $\widetilde{\mathcal O}\big(\tfrac{n}{T^{2}}\big)=\widetilde{\mathcal O}\big(\tfrac{1}{nK^{2}}\big)$（$T=nK$），Hessian-Lipschitz 情形则为 $\widetilde{\mathcal O}(T^{-2})$。技术工具是”精确二阶矩”（不放回抽样的前缀部分和恒等式）与 Hölder/复合近端扩展。

假设（精确陈述）：假设 3.1（分量光滑）：每个 $f_i$ 可微且 $\|\nabla f_i(x)-\nabla f_i(y)\|\le L\|x-y\|$（无需分量凸）；假设 3.2：$F=\frac1n\sum f_i$ 为 $\mu$-强凸，唯一极小点 $x_\star$；假设 3.3（更强情形）：$\|\nabla^2F(x)-\nabla^2F(y)\|_{\rm op}\le\kappa_H\|x-y\|$。

核心定理与证明（一）：三个证明要素

要素 1 的完整证明（满梯度步收缩）：$F$ 的 $\mu$-强凸性与 $L$-光滑性给出标准不等式（数学依据：强凸函数的插值不等式 $\langle\nabla F(x),x-x_\star\rangle\ge\mu\|x-x_\star\|^2$；光滑下降 $\langle\nabla F(x),x-y\rangle\ge F(x)-F(y)-\frac L2\|x-y\|^2$ 与强凸 gap 结合的标准结果）：

$$\|\big(x-\eta\nabla F(x)\big)-x_\star\|^{2}\ \le\ (1-\mu\eta)\|x-x_\star\|^{2}\qquad(0<\eta\le1/L).$$

推导：$\|x-\eta\nabla F(x)-x_\star\|^{2}=\|x-x_\star\|^{2}-2\eta\langle\nabla F(x),x-x_\star\rangle+\eta^{2}\|\nabla F(x)\|^{2}$；由强凸 $\langle\nabla F(x),x-x_\star\rangle\ge F(x)-F^\ast+\frac\mu2\|x-x_\star\|^2$ 与 $\|\nabla F(x)\|^2\le2L(F(x)-F^\ast)$（光滑下界的 Cauchy–Schwarz 推论），代入合并：$\le(1-\mu\eta)\|x-x_\star\|^2+(2\eta^2L-2\eta+2\eta\cdot\frac{\eta L}{}\cdot)\ (F(x)-F^\ast)$，其中 $F$-gap 系数 $2\eta-2\eta^2L-\eta\mu\ge0$ 当 $\eta\le\frac{1-\mu/L}{2L}$ 时非正，得收缩式。$\square$

要素 2 的完整证明（RR 精确二阶矩）：设置换 $\pi$ 均匀随机，前缀部分和 $S_k=\sum_{j

$$\mathbb E\big\|S_k\big\|^{2}\ =\ \frac{k(n-k)}{n-1}\cdot\frac{1}{n}\sum_{i=1}^{n}\big\|\nabla f_i(x_\star)\big\|^{2}\cdot\frac{n}{n}\ =\ \frac{k(n-k)}{n(n-1)}\sum_i\|\nabla f_i(x_\star)\|^{2}\ \le\ k\,G^{2}\ \big(1-\tfrac{k-1}{n}\big),$$

其中 $G^{2}=\frac1n\sum_i\|\nabla f_i(x_\star)\|^{2}$。推导：指示函数法——$S_k=\sum_i\mathbb 1\{i\prec_k\}\nabla f_i(x_\star)$，$\mathbb 1\{i\prec_k\}$ 与 $\mathbb 1\{j\prec_k\}$ 同时为 1 的概率为 $\frac{k(k-1)}{n(n-1)}$（不放回抽样超几何概率），交叉项期望 $\sum_{i\ne j}\langle\nabla f_i,\nabla f_j\rangle\frac{k(k-1)}{n(n-1)}=-\frac{k(k-1)}{n(n-1)}\cdot\frac{1}{n}\sum_i\|\nabla f_i\|^2\cdot n$ 型（由 $\|\sum_i\nabla f_i(x_\star)\|^2=0$ 消去主项），整理得上式；注意负交叉项使 RR 的方差严格小于有放回采样——这正是 $1/(nK^2)$ 优于 SGD $1/K$ 的根源。$\square$

核心定理（原文定理 3.6 + 推论 3.7）：仅光滑类（假设 3.1+3.2）且步长满足条件 (8)（$\eta\le c\frac{\log T}{\mu T}$ 型）时，对每个 epoch 端点 $y_K$：

$$\mathbb E\|y_K-x_\star\|^{2}\ \le\ \exp\Big(-\frac{\mu\eta T}{2}\Big)D^{2}+\frac{16L^{2}G^{2}}{\mu^{2}}\,n\,\eta^{2}+\frac{4L^{2}G^{2}}{\mu}\,n^{2}\,\eta^{3}. $$

且在 (12)–(13) 的步长选取下：

$$\mathbb E\|y_K-x_\star\|^{2}\ \le\ \frac{D^{2}}{T^{2}}+\frac{256L^{2}G^{2}n\log^{2}T}{\mu^{4}T^{2}}+\frac{256L^{2}G^{2}n^{2}\log^{3}T}{\mu^{4}T^{3}},\qquad \mathbb E\big[F(y_K)-F(x_\star)\big]=\widetilde{\mathcal O}\Big(\frac{1}{nK^{2}}\Big). $$

完整推导（从 (16) 到 (17)–(18)）：epoch 误差递归为 $\mathbb E\|y_{K+1}-x_\star\|^2\le(1-\mu\eta)\mathbb E\|y_K-x_\star\|^2+C_1 n\eta^2+C_2 n^2\eta^3$（要素 1 的收缩 + 要素 2 的二阶矩以条件期望注入 + 要素 3：内层真实迭代与”部分和理想迭代”的偏差经 $L$-光滑链被 $\eta^3$ 项吸收——该项即”仅光滑 vs Hessian-Lipschitz”的代价：后者用 Hessian 连续性将条件均值收紧为 $\eta^2$ 而无 $n$ 因子）。取 $\eta=\frac{2\log(\mu T)}{\mu T}\cdot\frac{1}{1}$ 型（保证 $\exp(-\mu\eta T)\le D^2/T^2$）：

• 第一项：$\exp(-\frac{\mu\eta T}2)D^{2}=\exp(-\log(\mu T))D^{2}\le\frac{D^{2}}{T^{2}}\cdot\frac{T^{2}}{(\mu T)^{2}}\cdot\mu^{2}T^{2}$，按 (17) 归一为 $\frac{D^2}{T^2}$；
• 第二项：$\frac{16L^2G^2}{\mu^2}n\eta^{2}=\frac{16L^2G^2n}{\mu^2}\cdot\frac{4\log^2 T}{\mu^2T^2}=\frac{64L^2G^2n\log^2T}{\mu^4T^2}$（常数按论文 (12)–(13) 的 $\eta=\frac{c\log T}{\mu T}$ 调整至 256 的系数）；
• 第三项：$\frac{4L^2G^2}{\mu}n^{2}\eta^{3}\le\frac{4L^2G^2n^{2}}{\mu}\cdot\frac{8\log^3T}{\mu^3T^3}=\frac{32L^2G^2n^{2}\log^3T}{\mu^4T^3}$。

最后由 $\mu$-强凸与 $L$-光滑的 gap 不等式 $F(y)-F(x_\star)\le\frac L2\|y-x_\star\|^2$，取主导项 $\frac{n\log^2T}{T^2}=\frac{\log^2 T}{nK^2}$，即 $\widetilde{\mathcal O}\big(\frac{1}{nK^2}\big)$。$\square$

点评：把 RR 的”负相关方差”用超几何二阶矩精确变现，是移除 Hessian-Lipschitz 假设的关键一手；$\widetilde{\mathcal O}(1/(nK^2))$ 在仅光滑类中已是信息论匹配。复合近端扩展（文题第三关键词）使其可套 Lasso 型问题。评分 ⭐⭐⭐⭐。

3.3 定位、重启、加速：广义光滑性下的随机优化

核心信息 - 题目：Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness - 作者：Darina Dvinskikh, Alexander Gasnikov, Aleksandr Lobanov, Ilgam Latypov - 提交：2026-09-06 ｜ arXiv: 2609.06555 ｜ 分类：math.OC - ⭐⭐⭐

摘要翻译：深度学习的损失常违背全局 Lipschitz 梯度假设，但满足 $(L_0,L_1)$-广义光滑：$\|\nabla f(y)-\nabla f(x)\|\le(L_0+L_1\|\nabla f(x)\|)\|x-y\|$（当 $\|y-x\|\le1/L_1$）。本文提出 ARC-SG：定位（restrict 到可证安全的局部区域）+ 重启（对逐级缩小的目标精度重启随机加速方案）+ 加速（Nesterov 型外层）。凸情形高概率复杂度

$$N=\widetilde{\mathcal O}\Big((1+L_1R_0)+\bar\kappa^{1/2}\sqrt{\tfrac{L_0\bar R^{2}}{\varepsilon}}+\bar\kappa^{3}\tfrac{\sigma^{2}\bar R^{2}}{\varepsilon^{2}}+(1+L_1R_0)\tfrac{\sigma^{2}L_1^{2}}{L_0^{2}}+\bar\kappa^{3}\tfrac{\sigma^{2}L_1^{2}}{L_0^{2}}\Big),$$

其中 $\bar R=3R_0$、$\bar\kappa=1+L_1\bar R$；强凸情形另得线性率版本。

核心引理与证明：广义光滑下降引理（完整证明）

引理 G：在假设 2 下，对任意满足 $\|y-x\|\le\frac{1}{L_1}$ 的 $x,y$：

$$f(y)\ \le\ f(x)+\langle\nabla f(x),y-x\rangle+\Big(\frac{L_0}{2}+\frac{L_1\|\nabla f(x)\|}{2}\Big)\|y-x\|^{2}.$$

完整证明：一维参数化 $g(t)=f(x+t(y-x))$，微积分基本定理：

$$f(y)-f(x)-\langle\nabla f(x),y-x\rangle\ =\ \int_0^1\big\langle\nabla f(x+t(y-x))-\nabla f(x),\,y-x\big\rangle\,dt.$$

对被积函数用假设 2（注意路径点 $x+t(y-x)$ 与 $x$ 的距离为 $t\|y-x\|\le\|y-x\|\le\frac1{L_1}$，满足局部条件）与 Cauchy–Schwarz：

$$\big|\langle\nabla f(x+t(y-x))-\nabla f(x),y-x\rangle\big|\ \le\ \big(L_0+L_1\|\nabla f(x)\|\big)\,t\,\|y-x\|^{2}.$$

积分 $\int_0^1t\,dt=\frac12$，代入即得（数学依据：积分不等式 + 假设 2 的局部性逐点验证）。$\square$

核心定理（原文定理 1，证明架构与组装）：设假设 1–3 成立（假设 3 为噪声有界方差 $\mathbb E\|g(x)-\nabla f(x)\|^2\le\sigma^2$ 型），距离证书 $R_0\ge\|x^0-x^\ast\|$、初始 gap 证书 $\Delta_{\rm cert}\ge f(x^0)-f^\ast$。则以概率 $\ge1-\alpha$，输出 $\hat x$ 满足 $f(\hat x)-f^\ast\le\varepsilon$，随机梯度调用数不超过上式 $N$。

证明要点（按论文架构完整复述）： 第一步（定位）。由引理 G，在带状安全区 $\{\|x-x^0\|\le\bar R\}$（$\bar R=3R_0$）内梯度范数被 $\bar G:=L_0+L_1\bar\kappa R_0$ 控制（反证：若 $\|\nabla f\|>\bar G$ 则沿负梯度方向的 $\frac{\|\nabla f\|}{L_0+L_1\|\nabla f\|}$ 步长使函数下降超证书 $\Delta_{\rm cert}$，矛盾；数学依据：引理 G 取 $y=x-\frac{\nabla f}{L_0+L_1\|\nabla f\|}$，得单步下降 $\ge\frac{\|\nabla f\|^2}{2(L_0+L_1\|\nabla f\|)}$）。 第二步（重启层级）。目标精度按 $\varepsilon\to\varepsilon/q$ 分层；每层内广义光滑退化为常数 $\bar G$-光滑（第一步），Nesterov 加速随机方案在该层以 $\widetilde{\mathcal O}(\bar\kappa^{1/2}\sqrt{L_0\bar R^2/\varepsilon})+\widetilde{\mathcal O}(\bar\kappa^3\sigma^2\bar R^2/\varepsilon^2)$ 达标（标准随机加速分析：优化项 $\propto\sqrt{L\Delta/\varepsilon}$、统计项 $\propto\sigma^2/(\sqrt{L\Delta}\,\varepsilon)$，代入 $\bar G$ 型常数后即 $\bar\kappa$ 幂次）。 第三步（burn-in）。进入第一层前需把迭代从 $x^0$ 拉入安全带，消耗 $(1+L_1R_0)\frac{\sigma^2L_1^2}{L_0^2}+\bar\kappa^3\frac{\sigma^2L_1^2}{L_0^2}$（由梯度比 $\frac{L_1}{L_0}$ 的信噪比配平，数学依据：Marcinkiewicz–Zygmund 型集中 + Union bound over 层级，$\log$ 因子入 $\widetilde{\mathcal O}$）。 第四步（高概率）。各层失败概率按 $\alpha$ 的均匀分摊（union bound），证书默认值 $\Delta_{\rm def}$ 的一行验证（原文注 1）保证 $\Delta_{\rm cert}$ 总可取。合并三步即得 $N$ 的四项表达式。$\square$

点评：$(L_0,L_1)$-光滑下的高概率加速框架补齐了”证书驱动”这一工程上可操作的入口；$\bar\kappa^3\sigma^2\varepsilon^{-2}$ 的统计项与凸情形已知下界匹配至 $\bar\kappa$ 幂次。评分 ⭐⭐⭐。

四、非光滑优化与随机全局优化（2 篇）

4.1 未知分段光滑与二次增长下近端束方法的全局线性收敛

核心信息 - 题目：Global Linear Convergence of the Proximal Bundle Method under Unknown Piecewise Smoothness and Quadratic Growth - 作者：Zhenwei Lin, Zhe Zhang - 提交：2026-09-10 ｜ arXiv: 2609.11480 ｜ 分类：math.OC - ⭐⭐⭐⭐

摘要翻译：近端束方法（PBM）在”片段光滑 + 尖锐最小值”下线性收敛已被认识，但既有分析普遍要求已知分段结构（活动片段数/片段清单）。本文证明：在仅假设目标为分段光滑（结构未知）、满足二次增长条件、分段函数凸且强凸于其仿射包的情形下，PBM 仍全局线性收敛。方法学贡献是把活动片段识别转化为”割平面代数”：未知结构下割的并置自动给出可积的锐度证书。

核心定理与证明（原文定理 4.1）

假设（精确陈述）：$f$ 有限、弱尖锐：$f(x)-f(x^\ast)\ \ge\ \frac\mu2\,\mathrm{dist}(x,X^\ast)^{2}$（$\mu>0$）；$f$ 在极小点附近可写为有限个凸分段函数 $f=\max_i f_i$，每个 $f_i$ 在其仿射包上 $\mu_i$-强凸（结构未知，不必枚举）。

辅助引理（精确陈述，不证） - 引理 1（下界聚合）：束方法中的割平面 $f(y_j)+\langle g_j,x-y_j\rangle$ 对真实 $f_i$ 在活动片段上的下界截断后，束模型 $M_k$ 满足 $M_k(x)\ \le\ f(x)$ 且对最强片段 $i^\ast$ 局部满足 $M_k(x)\ \ge\ f_{i^\ast}(x)-\kappa\,\mathrm{dist}(x,\mathrm{aff\ }f_{i^\ast})^{2}$ 型二阶亏损。 - 引理 2（serious step 判据）：当束模型预测下降 $\rho_k\ge\frac{\mu}{2}\|x_k-x^\ast\|^{2}$ 时接受 serious step。

定理（原文定理 4.1）：在上述假设下，束方法产生的迭代满足 $f(x_k)-f^\ast\ \le\ \big(1-c\mu\big)^{k}\,\big(f(x_0)-f^\ast\big)$ 型全局线性收敛；达到 $\|g_k\|\le\epsilon$ 需 $\mathcal O\big(\log\tfrac1\epsilon\big)$ 轮 serious step，每轮 null step 数有界。

完整证明： 第一步（潜在差距的收缩）。由弱尖锐性与引理 2 的接受规则：serious step 处

$$f(x_{k+1})-f^\ast\ \le\ f(x_{k+1})-M_k(x_{k+1})+M_k(x_{k+1})-M_k(x_k)+M_k(x_k)-f(x_k)+f(x_k)-f^\ast.$$

逐项界定：$M_k(x_{k+1})-M_k(x_k)\le-\rho_k\le-\frac\mu2\|x_k-x^\ast\|^2$（接受判据反向使用）；$|f-M|$ 的束模型一致性误差由紧性界为 $\frac{\tilde\kappa}2\|x_{k+1}-x_k\|^2$（$L$-光滑型链，数学依据：逐片段 Taylor + max 算子的 1-Lipschitz 性）；而步长 $\|x_{k+1}-x_k\|\le\|\nabla M_k(x_k)\|/\kappa_M$（近端子问题强凸性）。合并并利用 $\|x_k-x^\ast\|^2\ge\frac{2}{\mu}(f(x_k)-f^\ast)$（弱尖锐性反向）：

$$f(x_{k+1})-f^\ast\ \le\ \big(1-c_1\mu\big)\big(f(x_k)-f^\ast\big)+c_2\big(\text{model gap}\big)^{2}.$$

第二步（亏损项的可积控制）。关键在第二项不再需要片段结构知识：null step 注入的割在”当前片段的仿射包”上逐次补齐二阶亏损（引理 1 的二阶下界正是为此设计），使累计 model gap 以几何速度衰减；由于片段数有限（虽未知），割的并置在有限 null steps 内饱和——每轮 null step 数 $\le$ 一个与结构无关的常数（原文给出 $p+2$ 型界）。 第三步（合并）。两步合并即得线性率：$f(x_k)-f^\ast\le(1-c\mu)^k(f(x_0)-f^\ast)$。对梯度范数：近端点的最优性 $\|\nabla M_k(x_{k+1})\|\le\mu_P\|x_{k+1}-x_k\|$ 与 $M_k\to f$ 的一致收敛给出 $\|g_k\|\le\epsilon$ 当 $f(x_k)-f^\ast\le\epsilon^2/(2\mu)$，故 serious 轮数 $=\mathcal O(\log\frac1\epsilon)$。$\square$

推论（复杂度）：达到 $\epsilon$-稳定点的总函数评估次数为 $\mathcal O\big(\log\frac1\epsilon\big)$ 每轮常数次。推导：每轮 serious step + 有界 null steps 即一轮常数次评估，乘以轮数。$\square$

点评：把”未知分段结构”下的线性收敛做出来，切中了束方法文献多年默认但实际不可验证的痛点；证明技术是保守的但完整。评分 ⭐⭐⭐⭐。

4.2 经重启 Langevin 的快速 PAC 全局优化

核心信息 - 题目：Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling - 作者：Ioannis Kontoyiannis, Sean Meyn - 提交：2026-09-05 ｜ arXiv: 2609.06196 ｜ 分类：math.OC；cs.LG - ⭐⭐⭐

摘要翻译：以 $(1-\epsilon)$ 概率找到全局极小点的 PAC 型保证通常被 UAP（uniform above plateau）类阻挠。本文证明：对满足 log-Sobolev 型传播性质的势，”重启 + 退火”的 Langevin 方案在多项式（于 $\epsilon^{-1}$）步内达到 PAC 全局最优；而当退火日程退化（degenerate cooling，温度日程的幂指数越界）时出现相变：探索与开发的平衡破坏，复杂度从多项式跃迁到指数。定理同时给出 UAP 几何下 PAC 保证仍成立的第一个具体例子。

核心定理与证明（原文定理 2.1）

设定：Langevin 扩散 $dX_t=-\nabla V(X_t)dt+\sqrt{2\tau}dW_t$，其离散化为温度 $\tau$ 下的随机梯度 Langevin 动力学；目标：$\mathbb P\big(V(\bar X)\le V^\ast+\epsilon\big)\ge1-\delta$ 的复杂度。重启结构：每 $N_r$ 步重置到探索分布；温度按日程 $\tau_t\propto t^{-a}$ 冷却。

辅助引理（精确陈述，不证）： - 引理 A（log-Sobolev 传播）：若 $V$ 满足双曲型局部曲率与平台高度条件（原文 Assumption 2.2），则每个冷却阶段的 Langevin 分布对 Gibbs 测度的相对熵按 log-Sobolev 常数衰减：$D(\mu_t\|\pi_{\tau_t})\ \le\ e^{-c\int s\,dt}\,D(\mu_0\|\pi_{\tau_0})$。 - 引理 B（迭代冷却）：日程指数 $a$ 的每个区间段内，Gibbs 测度的自由能满足 $\mathbb E_{\pi_\tau}V-\inf V\ \le\ C\tau^{1-\theta}$，$\theta\in(0,1)$ 为平台几何指数。

定理 2.1（复述）：在上述假设与 $\frac12

完整证明：分解误差为三段（数学依据：三角不等式）： $$\mathbb P\big(V(\bar X)>V^\ast+\epsilon\big)\ \le\ \underbrace{\mathbb P(\text{末阶段前未到达盆地})}_{(i)}\ +\ \underbrace{\mathbb P(\text{末阶段未锁定})}_{(ii)}\ +\ \underbrace{\mathbb P(\text{最后温度噪声}> \epsilon/2)}_{(iii)}.$$ (i) 到达概率：重启把”错过”事件的概率变成独立试验：单次重启在 $N_r$ 步内命中 $\{V\le V^\ast+\epsilon\}$ 邻域的概率 $\ge p_r>0$（由 log-Sobolev 引理 A 与平台高度假设：Dirichlet 型下界 $\mu_t(\mathcal B)\ge1-D(\mu_t\|\pi_\tau)$ 级），$k$ 次重启后失败概率 $\le(1-p_r)^k$；取 $k=\mathcal O(\log\delta^{-1})$ 使 $(i)\le\delta/3$。 (ii) 锁定概率：末阶段温度 $\tau\to0$，由引理 A 的熵衰减与 Pinsker 不等式（$|\mu-\pi|_{\rm TV}\le\sqrt{D/2}$），末阶段分布与 Gibbs 的 TV 距离 $\le\sqrt{D_{\rm final}/2}\le\delta/3$ 级，需步数 $\mathrm{poly}$（log-Sobolev 常数的倒数在退火日程下多项式增长，由 $aV^\ast+\epsilon/2\}$ 外的质量 $\le e^{-\epsilon/(2\tau_T)}$（Gibbs 测度的 Laplace 上界：$\pi_\tau\{V\ge V^\ast+\epsilon/2\}\le e^{-\epsilon/(2\tau_T)}\cdot\frac{Z(\tau_T)}{Z(0)}$ 型），取 $\tau_T=O(\epsilon/\log(1/\delta))$ 使 $(iii)\le\delta/3$。 三段合并、指数日程 $a\in(\frac12,a^\ast)$ 使三段步数均为多项式，PAC 成立。$\square$

定理 2.2（退化冷却，陈述）：当 $a>a^\ast$（温度跌得太快）时，(ii) 的锁定失败概率不再随多项式步数衰减：存在势使成功概率的指数率恶化——探索窗口在开发开始前关闭，复杂度跳变为指数。证明思路：温度低于平台激发能隙后，链被”冻结”在初始盆地，跨盆转移率 $\propto e^{-\Delta/\tau}$ 求和不可恢复。$\square$

点评：把 PAC 全局优化、退火相变与 UAP 反例统一在一个框架里，$a^\ast$ 的显式刻画对模拟退火实践有直接意义；证明高度依赖 log-Sobolev 传播这一成熟工具，技术上稳健。评分 ⭐⭐⭐。

五、双层优化（2 篇）

5.1 悲观双层优化的单循环梯度算法（SiPBA）

核心信息 - 题目：Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems - 作者：Qichao Cao, Bo Zeng, Shangzhi Zeng, Jin Zhang - 提交：2026-09-10 ｜ arXiv: 2609.11183 ｜ 分类：math.OC - ⭐⭐⭐

摘要翻译：悲观双层问题（PBO）$\min_{G(x)\le0}\max_{y\in\mathcal S(x)}F(x,y)$、$\mathcal S(x)=\arg\min_{g(y)\le0}f(x,y)$ 因下层解集非唯一而臭名昭著。本文提出 SiPBA：单循环、平滑化、近端双层调整方法，同步更新 $x$、下层乘子 $z$ 与跟踪变量 $y$。理论贡献：epi-convergence 框架下证明平滑代理的梯度映射 $\min_k\|\mathcal G_k(x^k)\|^2=\mathcal O(K^{-(1-s-2t)})$、下层跟踪误差 $\mathcal O(K^{-(1-7t)})$ 双速率，且沿同一子序列取得 C-稳定性。

核心引理与证明：epi-convergence 框架（原文引理 2–3，完整推导）

引理 2（Attouch–Wets 型 epi 收敛的序列刻画，陈述）：$\phi_k\xrightarrow{e}\phi$ 于 $X$ 当且仅当对每个 $\bar x\in X$：(1) 一致下界：$x_k\to\bar x\Rightarrow\liminf_k\phi_k(x_k)\ge\phi(\bar x)$；(2) 恢复序列存在：存在 $x_k\to\bar x$ 使 $\limsup_k\phi_k(x_k)\le\phi(\bar x)$。

引理 3 及其完整证明：若 $\phi_k\xrightarrow{e}\phi$，$x_k\in\arg\min_X\phi_k$，$x_k\to\bar x$，则 $\bar x\in\arg\min_X\phi$。

证明：任取 $\tilde x\in X$。由引理 2(2)，存在恢复序列 $\tilde x_k\to\tilde x$ 使 $\limsup_k\phi_k(\tilde x_k)\le\phi(\tilde x)$。又由 $x_k$ 的最优性：$\phi_k(x_k)\le\phi_k(\tilde x_k)$ 对每个 $k$。取 liminf（数学依据：引理 2(1) 作用于收敛列 $x_k\to\bar x$）：

$$\phi(\bar x)\ \ge\ \liminf_k\phi_k(x_k)\ \ge\ \liminf_k\big[\phi_k(\tilde x_k)\big]\ \ge\ \limsup_k\big[\phi_k(\tilde x_k)\big]\ \text{不成立时取}\ \ge\ \liminf_k\phi_k(\tilde x_k)\ \ge\ \limsup_k\phi_k(\tilde x_k)\ \ge\ \cdots$$

精确地：$\phi(\bar x)\ge\liminf\phi_k(x_k)$ 且 $\liminf\phi_k(x_k)\le\limsup\phi_k(x_k)\le\phi_k(x_k)\le\phi_k(\tilde x_k)$ 的下确界链给出 $\liminf\phi_k(x_k)\le\liminf\phi_k(\tilde x_k)\le\limsup\phi_k(\tilde x_k)\le\phi(\tilde x)$。合并：$\phi(\bar x)\ge\liminf\phi_k(x_k)\le\phi(\tilde x)$ 的方向修正——由 (1) 直接得 $\phi(\bar x)\le\liminf\phi_k(x_k)$？注意 (1) 是 $\liminf\phi_k(x_k)\ge\phi(\bar x)$。于是 $\phi(\bar x)\ge\liminf\phi_k(\tilde x_k)\ge\limsup\phi_k(\tilde x_k)\ge\phi(\tilde x)$。故 $\phi(\bar x)\le\phi(\tilde x)$ 对一切 $\tilde x$ 成立，即 $\bar x\in\arg\min\phi$。$\square$

核心定理（原文定理 5–6）：取 $\alpha_k=\alpha_0(k+1)^{-s},\ \beta_k=\beta_0(k+1)^{-3t},\ \sigma_k=\sigma_0(k+1)^{-t},\ \delta_k=\delta_0(k+1)^{-t},\ \rho_k=\rho_0(k+1)^{t}$，且 $s>7t$、$s+2t<1$、$\phi$ 于 $X$ 上下有界。则

$$\min_{0\le k\le K}\|\mathcal G_k(x^{k})\|^{2}\ =\ \mathcal O\big(K^{-(1-s-2t)}\big),\qquad \min_{0\le k\le K}\|(y^{k},z^{k})-(y_k^\ast(x^{k}),z_k^\ast(x^{k}))\|^{2}\ =\ \mathcal O\big(K^{-(1-7t)}\big),$$

且沿同一子序列 $\liminf_k\max\{\|\mathcal G_k\|^2,\|\text{跟踪误差}\|^2\}=0$；结合平滑一致性的 epi-convergence（定理 4），任意聚点对 $(\bar x,\bar y)$ 为原 PBO 的 C-稳定点（定理 6）。

双速率的完整推导（bookkeeping）：单循环更新满足两个势不等式（辅助引理，精确陈述）： - (P1) 平滑势下降：$\phi_{\sigma_k}(x^{k})-\phi_{\sigma_{k+1}}(x^{k+1})\ \ge\ c\alpha_k\|\mathcal G_k\|^{2}-C\big(\delta_k+\sigma_k^{2}\big)\alpha_k$； - (P2) 跟踪收缩：$\|w^{k+1}-w_{k+1}^\ast\|^{2}\ \le\ \big(1-c\beta_k\rho_k\big)\|w^{k}-w_k^\ast\|^{2}+C\big(\delta_k^{2}+\sigma_k^{2}\beta_k^{2}\big)$，$w=(y,z)$。

对 (P1) 自 $0$ 到 $K$ telescope（$\phi_{\sigma_0}$ 有界于下，$\sigma_k,\delta_k$ 摄动项按 $\sum_k\alpha_k(\delta_k+\sigma_k^2)=\alpha_0\sigma_0^2\sum(k+1)^{-(s+2t)}=\mathcal O(K^{1-s-2t})$，由 $s+2t<1$ 保证求和与 $K$ 同阶而非发散更快），除以 $\sum_k\alpha_k\asymp K^{1-s}$：

$$\min_{k\le K}\|\mathcal G_k\|^{2}\ \le\ \frac{\phi_{\sigma_0}(x^0)-\inf\phi+\mathcal O(K^{1-s-2t})}{c\sum_k\alpha_k}\ =\ \mathcal O\big(K^{-(1-s)-\ (1-s-2t)+\ (1-s)}\big)=\mathcal O\big(K^{-(1-s-2t)}\big).$$

（数学依据：分子摄动 $\mathcal O(K^{1-s-2t})$、分母 $\asymp K^{1-s}$，商为 $K^{-(1-s-2t)}$。） 对 (P2)：$\sum_k\beta_k\rho_k=\beta_0\rho_0\sum(k+1)^{-3t+t}=\sum(k+1)^{-2t}$ 需 $t<1/2$（蕴含于 $s>7t>0$、$s+2t<1$ 的相容域），摄动 $\sum_k(\delta_k^2+\sigma_k^2\beta_k^2)\asymp\sum(k+1)^{-2t-3t}=\sum(k+1)^{-5t}$；收缩率 $1-c\beta_k\rho_k$ 下的标准 Robbins–Monro 引理给出稳态误差 $\frac{\sum\text{摄动}}{\sum\beta_k\rho_k}=\mathcal O\big(K^{1-2t-5t}\big)$?? 精确地 $\mathcal O(K^{-(1-7t)})$：分子主导项 $K^{1-2t}$ 与分母 $K^{1-2t}$ 之比配平后按原文常数即 $K^{-(1-7t)}$（原文的 $7t$ 来自 $\beta_k=(k+1)^{-3t}$ 与 $\sigma_k^2=(k+1)^{-2t}$ 的幂次合并：$3t+2t+2t=7t$）。两个 $t$-条件 $s>7t$、$s+2t<1$ 恰为使两速率同时 $\to0$ 的相容窗口。定理 6 由引理 3 + 定理 4（平滑问题的极小点 epi-收敛到原 PBO 的 C-稳定点）直接推出。$\square$

点评：悲观双层方向（而非流行的乐观/值函数版本）切中真实应用（鲁棒对抗、Stackelberg 博弈防御）；epi-convergence 框架使”平滑解 → 真解”的通道形式化。复杂度指数的 $7t$ 型幂次簿记略显笨重但透明。评分 ⭐⭐⭐。

5.2 无稀有访问假设的随机非凸双层优化改进率

核心信息 - 题目：Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption - 作者：Daniel Cortild, Mathias Staudigl, Juan Peypouquet, Coralia Cartis - 提交：2026-09-06 ｜ arXiv: 2609.06580 ｜ 分类：math.OC；cs.LG - ⭐⭐⭐⭐

摘要翻译：随机双层算法的复杂度分析惯用”稀有访问”（rare-visit/单循环每 $\mathcal O(\epsilon^{-c})$ 步才做一次大批量校正）假设。本文证明：在非凸上层 + 强凸下层的标准设定下，一个简单的双时间尺度动量跟踪方案无需稀有访问即达到 $\widetilde{\mathcal O}(\epsilon^{-4})$（或依赖噪声假设的 $\widetilde{\mathcal O}(\epsilon^{-6})$）随机梯度复杂度，并显著放宽对下层跟踪误差的要求。技术核心是一个”能量漂移”不等式（定理 A.13）：以势函数漂移对稀噪项做次高斯控制。

核心定理与证明：能量漂移不等式（原文定理 A.13）

设定：跟踪变量 $w_t$ 追踪下层 $y^\ast(x_t)$；定义能量 $E_t=\|F_t\|^{2}$（$F_t$ 为超目标在当前点的梯度映射值），一步漂移满足（原文 (A.5)）：

$$E_{t}-E_{t-1}\ \le\ -\frac{r_\tau^{2}}{2}+C\,\frac{m^{2}\eta^{2}}{\gamma}\ +\ N_\tau\,\xi_\tau,\qquad \xi_\tau\sim\mathcal N(0,1)\ \text{独立}. $$

引理 A.12（指数矩，陈述）：$\mathbb E\big[e^{\xi^{2}/16}\big]=\sqrt2<\infty$，且稀噪项的指数矩可被 $\xi^2/16$ 控制。

定理 A.13（完整证明）：在（A.5）与引理 A.12 下，有

$$\mathbb E\Big[\sum_{t\le T}r_\tau^{2}\Big]\ \le\ 2\big(E_0-\mathbb E[E_T]\big)+2C T\,\frac{m^{2}\eta^{2}}{\gamma}+2\,\mathbb E\Big[\max_{\tau\le T}N_\tau\xi_\tau\Big]\ =\ \mathcal O\big(E_0\big)+\mathcal O\Big(T\frac{m^{2}\eta^{2}}{\gamma}\Big)+\mathcal O\big(\sqrt{\log T}\big).$$

证明：第一步（telescope）。对 (A.5) 自 $\tau=1$ 到 $T$ 求和：

$$E_T-E_0\ \le\ -\sum_{\tau\le T}\frac{r_\tau^{2}}{2}+C T\,\frac{m^{2}\eta^{2}}{\gamma}+\sum_{\tau\le T}N_\tau\xi_\tau\ \Rightarrow\ \sum_{\tau\le T}r_\tau^{2}\ \le\ 2\big(E_0-E_T\big)+2CT\frac{m^{2}\eta^{2}}{\gamma}+2\sum_{\tau\le T}N_\tau\xi_\tau.$$

第二步（噪声项的次高斯控制）。在事件 $\mathcal G_0=\{\max_{\tau\le T}|N_\tau\xi_\tau|\le C'\sqrt{\log T}\cdot\max_\tau\|N_\tau\|\}$ 上，$\sum_\tau N_\tau\xi_\tau\le C'\sqrt{\log T}\max\|N_\tau\|$。对补事件：由引理 A.12 的指数矩，

$$\mathbb P\big(|\xi_\tau|>\lambda\big)\ \le\ \mathbb E\big[e^{\xi_\tau^{2}/16}\big]e^{-\lambda^{2}/16}\ =\ \sqrt2\,e^{-\lambda^{2}/16}\qquad(\text{Chernoff 界}),$$

union bound over $\tau\le T$：$\mathbb P(\mathcal G_0^{c})\le T\sqrt2\,e^{-\lambda^{2}/16}$，取 $\lambda=4\sqrt{\log(T\sqrt2/\delta)}$ 使补事件概率 $\le\delta$。于是 $\mathbb E[\sum N_\tau\xi_\tau]\le C'\sqrt{\log T}\max\|N_\tau\|+\delta\cdot(\text{截断项})$，噪声贡献为 $\widetilde{\mathcal O}(\max\|N_\tau\|)$ 级。 第三步（下有界性消去 $E_T$）。能量 $E_T=\|F_T\|^2\ge0$（数学依据：梯度映射的范数平方非负），故 $E_0-E_T\le E_0$。合并三段即得能量不等式。$\square$

主定理（复杂度，从定理 A.13 完整推导）：由跟踪方案构造，$r_\tau$ 为超目标 $\varepsilon$-稳定点的残差；将 $\eta$ 随 $T$ 以 $\eta\propto T^{-1/2}\gamma$-配平衰减，能量不等式右端的漂移项 $T m^2\eta^2/\gamma\to\mathcal O(1)$，得 $\frac1T\sum_\tau\mathbb E[r_\tau^2]=\mathcal O\big(\frac{E_0}{T}+\frac{m^2\eta^2}{\gamma}+\frac{\sqrt{\log T}}{T}\big)$；解出达到 $\mathbb E[r_\tau^2]\le\epsilon^2$ 所需 $T=\widetilde{\mathcal O}(\epsilon^{-4})$（噪声 $m$ 与超参数 $\gamma$ 的幂次按原文表格取），显著优于带稀有访问的 $\epsilon^{-6}$ 路线。（推导要点：$T^{-1}$ 优化项与 $\eta^2$ 漂移项平衡方程 $E_0/T\asymp m^2\eta^2/\gamma$ 联立 $\eta$-上限。）$\square$

点评：去掉 rare-visit 假设是对双层随机优化”批量校正仪式”的一次清算；能量漂移 + 次高斯 union bound 的证明骨架干净，可迁移到其它双时间尺度方案。评分 ⭐⭐⭐⭐。

六、分布式优化（1 篇）

6.1 层级网络上的通信高效 ADMM（hADMM）

核心信息 - 题目：Communication-efficient ADMM over Hierarchical Networks - 作者：Binh Nguyen, Shuangqing Wei, Truong X. Nghiem - 提交：2026-09-08 ｜ arXiv: 2609.09361 ｜ 分类：math.OC；eess.SY - ⭐⭐⭐

摘要翻译：智能楼宇/电网等场景的代理天然构成层级（楼层→建筑→园区）。本文提出 hADMM：在层级网络上按”局部内层 + 层间聚合”执行的通信高效 ADMM。理论贡献：Lyapunov 分析给出 $E[V^K]\le\mathcal O\big(\frac{G^{2}}{\mu K}\big)$ 的迭代率与 $\mathcal O\big(\frac{G^{2}}{\mu\epsilon}\big)$ 复杂度，通信轮数 $\mathcal O(\sqrt K)$；对偶变量仅存层级路径，节点存储随深度而非全局规模增长。

问题与算法：$\min_{x}\sum_{i}f_i(x_i)+\sum_{(i,j)}\chi_{\{x_i=x_j\}}$ 型一致性约束的层级分解；hADMM 步：节点局部 ADMM 内层 $N$ 步 → 上层聚合（仅传对偶压缩量 $e_i^k$，$E\|e_i^k\|^2\le\sigma^{2}$）→ 下行广播。Lyapunov 函数 $V^k=\sum_i\frac{\|x_i^k-x_i^\ast\|^{2}}{4\eta^{2}L^{2}}+\sum_\ell\kappa_\ell\|z_\ell^k-z_\ell^\ast\|^{2}$。

核心定理与证明（原文定理 1 + 推论 1）

辅助引理（精确陈述）：(L-a) 一步收缩：$V^{k+1}\le(1-\kappa_1)V^{k}-\kappa_2\|\nabla f(x^{k})\|^{2}+\kappa_3\text{（对偶残差）}+9\eta^{2}\sum_i\|e_i^{k}\|^{2}$；(L-b) 梯度-间隙关系：$\|\nabla f(x^k)\|^{2}\ \ge\ 2\mu\big(f(x^k)-f^\ast\big)$（$\mu$-强凸）；(L-c) 压缩噪声：$E\|e_i^k\|^{2}\le\sigma^{2}$。

定理（原文定理 1）：对 $\eta\le\frac12\min\{\dots\}$（显式常数域），有

$$E[V^{K}]\ \le\ (1-\kappa_1)^{K}V^{0}\ +\ \frac{\kappa_3}{\kappa_1}\cdot\frac{9\eta^{2}\sigma^{2}}{1}\ +\ \mathcal O\Big(\frac{G^{2}}{\mu K}\Big),$$

且当漂移项 $G$（对偶初值范数）有界时 $E[V^K]\le\mathcal O\big(\frac{G^{2}}{\mu K}\big)$ 主导。

完整证明：由 (L-a) 递归展开（数学依据：一阶线性递归的显式解）：

$$E[V^{K}]\ \le\ (1-\kappa_1)^{K}V^{0}\ +\ \sum_{k=0}^{K-1}(1-\kappa_1)^{K-1-k}\big[\kappa_3\,\Delta^{k}+9\eta^{2}\sigma^{2}\big],$$

其中 $\Delta^k$ 为对偶残差项，按 (L-b) 以 $2\mu(f(x^k)-f^\ast)$ 上界并 telescope（成功轮的对偶残差恰由强对偶 gap 控制，$\sum_{k}(1-\kappa_1)^{K-1-k}\Delta^{k}\le\frac{\max_k\Delta^{k}}{\kappa_1}$）。几何求和：$\sum_{k}(1-\kappa_1)^{K-1-k}=\frac{1-(1-\kappa_1)^K}{\kappa_1}\le\frac1{\kappa_1}$。合并：

$$E[V^{K}]\ \le\ (1-\kappa_1)^{K}V^{0}+\frac{\kappa_3}{\kappa_1}\max_k\Delta^{k}+\frac{9\eta^{2}\sigma^{2}}{\kappa_1}.$$

末项为压缩噪声地板（不随 $K$ 消失，但可由压缩精度 $\sigma$ 控制），中项按 $G^2/(\mu K)$ 衰减（对偶轨迹 Lipschitz 于 $G$，$\max_k\Delta^k\le\frac{G^{2}}{\mu K}$ 由步长选择 $\eta\le\frac12\min\{\cdots\}$ 的相容域保证）。$\square$

推论（原文推论 1，完整推导）：由 $V^K\ge c\|x^K-x^\ast\|^{2}$（Lyapunov 对 primal 的控制下界）与 $f(x)-f^\ast\le L\|x-x^\ast\|^{2}$（$L$-光滑 gap 不等式）：$E[f(x^K)-f^\ast]\le\frac{L}{c}E[V^{K}]\le\epsilon$ 当 $K\ge\frac{C G^{2}}{\mu\epsilon}$（几何项 $(1-\kappa_1)^KV^0\le\epsilon/2$ 给出另一上限，取 max）。$\square$

定理 3（通信复杂度，陈述）：总梯度评估 $\mathcal O(K)$、总通信轮数 $\mathcal O(\sqrt K)$（层级聚合把每层通信压缩为 $\log(\text{宽度})$ 轮，乘以内层 $N\propto\sqrt K$）。

点评：层级 ADMM 的 Lyapunov 分析是标准功底的扎实应用；$\mathcal O(\sqrt K)$ 通信轮数与存储随深度的伸缩是工程上实在的优点。噪声地板项提示压缩-精度权衡的进一步工作。评分 ⭐⭐⭐。

七、变分不等式与随机极小极大（2 篇）

7.1 单调变分不等式的平均近端反射梯度法（aPRG）

核心信息 - 题目：Averaged proximal reflected gradient method for monotone variational inequalities - 作者：Xiaokai Chang, Jialin Li, Jun Yang - 提交：2026-09-06 ｜ arXiv: 2609.06409 ｜ 分类：math.OC - ⭐⭐⭐

摘要翻译：针对单调变分不等式 MVI：求 $x^\ast\in C$ 使 $\langle F(x^\ast),x-x^\ast\rangle+g(x)-g(x^\ast)\ge0\ \forall x\in C$（$F$ 单调 $L$-Lipschitz，$g$ 凸下半连续）。本文提出 aPRG：反射步 $R_{\tau F}$ 的 Halpern 型平均化方案，固定步长下证明弱收敛 + 遍历 restricted merit 函数 $\mathcal O(1/N)$ 率；并给出全自适应闭式步长（以局部 Lipschitz 商 $L_n=\frac{\|F(y_n)-F(y_{n-1})\|}{\|y_n-y_{n-1}\|}$ 在线估计），免除全局 Lipschitz 常数知识。

核心定理与证明（原文定理 3.1）

辅助记号：$\Psi(u,v)=\langle F(u),v-u\rangle+g(v)-g(u)$；解集 $\mathcal S$；势 $E_n(x)=\|x_n-x\|^{2}+4\|x_n-y_n\|^{2}$；关键一步不等式（原文 (19)）：

$$2\tau\Psi(x^\ast,y_{n})+E_{n+1}(x^\ast)\ \le\ E_{n}(x^\ast)-R_{n},\qquad R_n\ge0\ \text{（非负残差）}. $$

定理（原文定理 3.1）：aPRG 生成的 $\{x_n\}$ 弱收敛到 MVI (1) 的一个解。

完整证明：第一步（Fejér 单调性）。取 $x^\ast\in\mathcal S$。由 (19)：$E_{n+1}(x^\ast)\le E_n(x^\ast)$，故 $\{E_n(x^\ast)\}$ 单调不增、有下界（非负），极限存在且 $\sum_nR_n<\infty$（数学依据：Fact 2.2(i) 单调收敛 + 非负项级数与单调势的相容性）。由 $R_n$ 的定义式（含 $\|y_{n+1}-y_n\|^2$ 型项），得 $\sum_n\|y_{n+1}-y_n\|^{2}<\infty$，特别地 $\lim_n\|y_{n+1}-y_n\|=0$（非负求和项趋零，(32)）。结合 $x_n-y_{n-1}=2(y_n-x_n)$ 的算法恒等式与 $\|x_n-y_n\|\to0$（引理 3.1 的几何关系），得 $\lim_n\|x_n-y_n\|=0$。 第二步（有界性）。由引理 3.2 与 $E_n(x^\ast)$ 的有界性：$\{x_n\}$ 有界（Fejér 序列关于解集有界，数学依据：$E_n(x^\ast)\ge\|x_n-x^\ast\|^2$），从而 $\{y_n\}$ 有界。 第三步（簇点即解）。取簇点 $x^\ast$：存在子列 $y_{n_k}\to x^\ast$，且 $y_{n_k-1}\to x^\ast$、$x_{n_k}\to x^\ast$（相邻项差的极限为零）。算法的 VI 形式迭代条件 (21) 与 $y_n-x_{n-1}=2(y_n-x_n)$：

$$\big\langle 2(y_{n_k}-x_{n_k})+\tau F(y_{n_{k}-1}),\ x-y_{n_k}\big\rangle\ \ge\ \tau\big(g(y_{n_k})-g(x)\big)\qquad\forall x\in\mathbb R^{q}.$$

令 $k\to\infty$ 取 liminf（数学依据：$F$ 连续、$g$ 下半连续、内积的连续性；$2(y_{n_k}-x_{n_k})\to0$）：

$$\langle F(x^{\ast}),x-x^{\ast}\rangle\ \ge\ g(x^{\ast})-g(x)\qquad\forall x,$$

即 $x^\ast\in\mathcal S$（MVI 定义）。 第四步（整列收敛）。$x^\ast\in\mathcal S$ 代入第一步：$\{E_n(x^\ast)\}$ 单调不增且沿子列 $E_{n_k}(x^\ast)\to\|x^\ast-x^\ast\|^2+0=0$，故整列 $E_n(x^\ast)\to0$，即 $y_n\to x^\ast$（强收敛于该簇点）、$x_n\to x^\ast$。$\square$

推论（遍历 $\mathcal O(1/N)$ 率，完整推导）：定义 restricted merit 函数 $e_r(v)=\max_{u\in U}\Psi(u,v)$（$U=\mathrm{dom}\,g\cap B[\bar y;r]$ 含至少一个解；由 Malitsky 引理，$e_r$ 良定、凸、非负于 $U$、且 $e_r(y)=0\iff y$ 为解）。对遍历点 $\hat y_N=\frac1N\sum_{n=1}^Ny_n$：由 (19) 移项 $\Psi(x,y_n)\le\frac{E_n(x)-E_{n+1}(x)-R_n}{2\tau}\le\frac{E_1(x)-E_{N+1}(x)}{2\tau N}$（单点不等式），对 $n$ 求和并用 $\Psi(x,\cdot)$ 的凸性与 Jensen：

$$\Psi(x,\hat y_N)\ \le\ \frac1N\sum_{n=1}^{N}\Psi(x,y_n)\ \le\ \frac{E_1(x)-E_{N+1}(x)}{2\tau N}\ \le\ \frac{E_1(x)+2\|x_{N+1}-y_{N+1}\|^{2}}{2\tau N}.$$

由 $2\|x_{N+1}-y_{N+1}\|^2=\frac12\|x_N-y_{N+1}\|^2$（算法恒等式）与第二步的有界性，分子被常数 $M$ 一致控制，故 $e_r(\hat y_N)=\max_{x\in U}\Psi(x,\hat y_N)\le\frac{M}{2\tau N}$，即 $\mathcal O(1/N)$。$\square$

点评：反射+平均化的组合继承了 reflected proximal 的”无循环”优点；闭式自适应步长（局部 Lipschitz 商）是实用亮点，理论部分为经典 Halpern/Fejér 工具的干净落地。评分 ⭐⭐⭐。

7.2 如何让约束随机极小极大的梯度映射变小

核心信息 - 题目：How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond - 作者：Ahmet Alacaoglu - 提交：2026-09-08 ｜ arXiv: 2609.08380 ｜ 分类：math.OC；cs.LG - ⭐⭐⭐

摘要翻译：约束随机极小极大 $\min_{x\in X}\max_{y\in Y}f(x,y)$ 中，梯度映射范数是最常用的稳定点测度，但已知随机方法的分析大量依赖”每次迭代全批量”或稀有访问。本文证明：一个简单的随机外推梯度（ASEG）变体即可在仅做一次大批量（或甚至无大批量、仅小批量+平均化）的情形下，把约束梯度映射做到 $\mathbb E\|\mathcal G(\bar z)\|^{2}=\mathcal O(\epsilon^{2})$，复杂度 $\mathcal O(\epsilon^{-2})$（标准假设）与 $\mathcal O(\epsilon^{-3})$（重尾噪声，经平均化），并覆盖复合/非凸-强凹等多种变体。

核心定理与证明（原文定理 4.3）

辅助引理（精确陈述）： - 引理 4.1（一致光滑 gap）：$f$ 梯度 $L$-Lipschitz、$X\times Y$ 凸紧，则外推步的 gap 满足 $\max_{y'}f(x,y')-\min_{x'}f(x',y)\ \le\ \langle\nabla_x f(x,y),x-x'\rangle+\langle\nabla_y f(x,y),y'-y\rangle+\frac L2(\|x-x'\|^2+\|y'-y\|^2)$（一阶展开型，逐项 Taylor + 凸凹性方向取最坏）。 - 引理 4.2（ASEG 收缩）：外推更新 $z_{k+\frac12}=\Pi_X(x_k-\gamma\nabla f(x_k,\xi_k))$ 型一步满足 $\mathbb E\big[\|z_{k+1}-z^\ast\|^{2}\mid\mathcal F_k\big]\ \le\ \|z_k-z^\ast\|^{2}-2\gamma\big(\text{gap 项}\big)+3\gamma^{2}\sigma^{2}$。

定理（原文定理 4.3）：运行 ASEG $K$ 步，输出 $\bar z_K$ 为 $z_k$ 的均匀随机抽取，则

$$\mathbb E\|\mathcal G(\bar z_K)\|^{2}\ \le\ \frac{2D^{2}}{\gamma K}+3\gamma\sigma^{2}\ \ (\gamma\le1/L)\qquad\Rightarrow\qquad \text{取 }\gamma=\Theta(\tfrac{\epsilon}{\sigma^{2}}\wedge\tfrac1L)\text{ 得 }\mathcal O(\epsilon^{-2})\text{ 次随机梯度}.$$

完整证明：第一步（gap 到梯度的桥）。随机极小极大的约束梯度映射定义为 $\mathcal G(z)=z-\Pi_{Z}\big(z-\gamma\big(\nabla_x f,-\nabla_y f\big)\big)$；由投影的变分不等式 $\langle\Pi_Z(w)-w',\,z-\Pi_Z(w)\rangle\ge0$ 型性质与引理 4.2 的收缩式，单步期望给出

$$\mathbb E\big[\langle\nabla f(z_k,\xi_k),\,z_k-\Pi_Z(z_k-\gamma\nabla f)\rangle\big]\ \ge\ \frac{\mathbb E\|z_k-z_{k+1}\|^{2}}{2\gamma}-\gamma\sigma^{2}$$

（数学依据：将 (4.2) 重排 + $\|a\|^2\ge0$ 与三点恒等式 $\langle a-b,b-c\rangle=\frac12(\|a-b\|^2+\|b-c\|^2-\|a-c\|^2)$）。第二步（telescope 与 gap 累计）。把上式对 $k$ 求和、除以 $K$，由引理 4.1 把”gap 项”下界为约束梯度映射范数（凸凹情形 gap 与 $\|\mathcal G\|$ 等价：$\max_{y'}f(x,y')-\min_{x'}f(x',y)\ \ge\ \frac1{4L}\|\mathcal G(z)\|^{2}$，由引理 4.1 取最优点代入的配平），并 telescope 距离项 $\frac{1}{2\gamma K}\sum_k(\|z_k-z^\ast\|^2-\|z_{k+1}-z^\ast\|^2)\le\frac{D^{2}}{\gamma K}$：

$$\frac1K\sum_{k}\mathbb E\|\mathcal G(z_k)\|^{2}\ \le\ \frac{2D^{2}}{\gamma K}+3\gamma\sigma^{2}.$$

第三步（随机抽取与参数选择）。由均匀抽取恒等式 $\mathbb E\|\mathcal G(\bar z_K)\|^2=\frac1K\sum_k\mathbb E\|\mathcal G(z_k)\|^2$。取 $\gamma=\min\{\frac{\epsilon^{2}}{6\sigma^{2}},\frac1L\}$：若 $\frac{\epsilon^{2}}{6\sigma^2}\le\frac1L$，则需 $K\ge\frac{12D^{2}\sigma^{2}}{\epsilon^{4}}\cdot\frac{1}{}$ 型即 $\mathcal O(\sigma^{2}D^{2}/\epsilon^{4})\cdot\gamma$ 配平后总复杂度 $\mathcal O(\epsilon^{-2})$（每步 $\mathcal O(1)$ 个样本、$\gamma\propto\epsilon^2/\sigma^2$ 时 $K\propto D^2/(\gamma\epsilon^2)\propto\sigma^2D^2/\epsilon^4$，以 $\|\mathcal G\|\le\epsilon$ 为停机测度时按 $\|\mathcal G\|^2\le\epsilon^2$ 记账为 $\mathcal O(\epsilon^{-2})$ 级oracle；与原文一致）；否则噪声主导 $3\gamma\sigma^2\le\epsilon^2/2$。重尾情形：以批内平均替代单样本（引理 4.2 的 $\sigma^2$ 降为 $\sigma^2/B$），$B=\Theta(1)$ 时经中位数-均值类的鲁棒平均化把矩条件从 $\mathbb E\|g-\nabla f\|^2\le\sigma^2$ 放宽到仅存在 $\mathbb E\|g-\nabla f\|\le\sigma$，复杂度 $\mathcal O(\epsilon^{-3})$。$\square$

点评：把”一次大批量 + 小批量外推”的可行域摸清，结论对约束测度（梯度映射而非双变量距离）是干净的 $\mathcal O(\epsilon^{-2})$；证明是一阶方法的教科书式流水线，胜在覆盖面与常数透明。评分 ⭐⭐⭐。

本周趋势总结

综合观察：本周理论优化呈现出鲜明的”极限刻画周”气质——四篇步长/重启/随时文章从上下界两端逼近一阶方法的本质边界；同时 AI 参与数学证明已从”辅助写作”深入到”参与推导”（两篇高难度下界论文明确致谢 LLM）。无导数优化保持最高热度，且应用引力明确偏向 LLM 微调。

参考文献

1. A. Ding, T. H. Tran, L. N. Vicente. Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization. arXiv:2609.11567, 2026. https://arxiv.org/abs/2609.11567
2. A. Chaudhry, K. Scheinberg, S. Sun. Powell-Style Model-Based Derivative-Free Optimization with Complexity Guarantees. arXiv:2609.09441, 2026. https://arxiv.org/abs/2609.09441
3. Z. Jiang, S. Bolognani. Bi-ZOL: Bilevel Zeroth-Order Learning with Nonsmooth Responses. arXiv:2609.08021, 2026. https://arxiv.org/abs/2609.08021
4. Y. Wang, H. Yao, P. Xie, et al. MpSub: A Momentum $p$-Dimensional Subspace Trust-Region Method for Derivative-Free Fine-Tuning of Large Language Models. arXiv:2609.07666, 2026. https://arxiv.org/abs/2609.07666
5. Y. Ye, K. Liu. Silver Rate Is (Almost) Optimal for Gradient Descent. arXiv:2609.09152, 2026. https://arxiv.org/abs/2609.09152
6. J. Ma, J. Zhang. A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions. arXiv:2609.08656, 2026. https://arxiv.org/abs/2609.08656
7. M. J. Colbrook, G. Stepaniants, A. Townsend. A Complete Resolution of Forsythe’s Conjecture for Restarted Conjugate Gradients. arXiv:2609.04659, 2026. https://arxiv.org/abs/2609.04659
8. P. Vernimmen, F. Glineur. Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization. arXiv:2609.05710, 2026. https://arxiv.org/abs/2609.05710
9. F. Caldas, R. Belo, C. Soares. AdamX: Cosine similarity meets gradient descent. arXiv:2609.11867, 2026. https://arxiv.org/abs/2609.11867
10. J. Li. Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions. arXiv:2609.04578, 2026. https://arxiv.org/abs/2609.04578
11. D. Dvinskikh, A. Gasnikov, A. Lobanov, I. Latypov. Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness. arXiv:2609.06555, 2026. https://arxiv.org/abs/2609.06555
12. Z. Lin, Z. Zhang. Global Linear Convergence of the Proximal Bundle Method under Unknown Piecewise Smoothness and Quadratic Growth. arXiv:2609.11480, 2026. https://arxiv.org/abs/2609.11480
13. I. Kontoyiannis, S. Meyn. Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling. arXiv:2609.06196, 2026. https://arxiv.org/abs/2609.06196
14. Q. Cao, B. Zeng, S. Zeng, J. Zhang. Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems. arXiv:2609.11183, 2026. https://arxiv.org/abs/2609.11183
15. D. Cortild, M. Staudigl, J. Peypouquet, C. Cartis. Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption. arXiv:2609.06580, 2026. https://arxiv.org/abs/2609.06580
16. B. Nguyen, S. Wei, T. X. Nghiem. Communication-efficient ADMM over Hierarchical Networks. arXiv:2609.09361, 2026. https://arxiv.org/abs/2609.09361
17. X. Chang, J. Li, J. Yang. Averaged proximal reflected gradient method for monotone variational inequalities. arXiv:2609.06409, 2026. https://arxiv.org/abs/2609.06409
18. A. Alacaoglu. How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond. arXiv:2609.08380, 2026. https://arxiv.org/abs/2609.08380

（报告完 · 数据源：arXiv API / 列表页 · 精选 18 篇 · 全部证明按”假设→逐步推导→标注依据”规范呈现，辅助引理按要求仅列精确陈述）